Contributions to the Theory of Finite-State Based Grammars

This dissertation is a theoretical study of finite-state based grammars used in natural language processing. The study is concerned with certain varieties of finite-state intersection grammars (FSIG) whose parsers define regular relations between surface strings and annotated surface strings. The study focuses on the following three aspects of FSIGs: (i) Computational complexity of grammars under limiting parameters In the study, the computational complexity in practical natural language processing is approached through performance-motivated parameters on structural complexity. Each parameter splits some grammars in the Chomsky hierarchy into an infinite set of subset approximations. When the approximations are regular, they seem to fall into the logarithmic-time hierarchyand the dot-depth hierarchy of star-free regular languages. This theoretical result is important and possibly relevant to grammar induction. (ii) Linguistically applicable structural representations Related to the linguistically applicable representations of syntactic entities, the study contains new bracketing schemes that cope with dependency links, left- and right branching, crossing dependencies and spurious ambiguity. New grammar representations that resemble the Chomsky-Schützenberger representation of context-free languages are presented in the study, and they include, in particular, representations for mildly context-sensitive non-projective dependency grammars whose performance-motivated approximations are linear time parseable. (iii) Compilation and simplification of linguistic constraints Efficient compilation methods for certain regular operations such as generalized restriction are presented. These include an elegant algorithm that has already been adopted as the approach in a proprietary finite-state tool. In addition to the compilation methods, an approach to on-the-fly simplifications of finite-state representations for parse forests is sketched. These findings are tightly coupled with each other under the theme of locality. I argue that the findings help us to develop better, linguistically oriented formalisms for finite-state parsing and to develop more efficient parsers for natural language processing. Avainsanat: syntactic parsing, finite-state automata, dependency grammar, first-order logic, linguistic performance, star-free regular approximations, mildly context-sensitive grammars

A Floor Control Server in a Distributed Conference Service

The conferencing systems in IP Multimedia (IM) networks are going through restructuring, accomplished in the near future. One of the changes introduced is the concept of floors and floor control in its current form with matching entity roles. The Binary Floor Control Protocol (BFCP) is a novelty to be exploited in distributed tightly coupled conferencing services. The protocol defines the floor control server (FCS), which implements floor control giving access to shared resources. As the newest tendency is to distribute the conferencing services, the locations of different functionality units play an important role in developing the standards. The floor control server location is not yet single-mindedly fixed in different standardization bodies, and the debate goes on where to place it within the media server, providing the conferencing service. The thesis main objective is to evaluate two distinctive alternatives in respect the Mp interface protocol between the respective nodes, as the interface in relation to floor control is under standardization work at the moment. The thesis gives a straightforward preamble in IMS network, nodes of interest including floor control server and conferencing. Knowledge on several protocols – BFCP, SDP, SIP and H.248 provides an important background for understanding the functionality changes introduced in the Mp interface and therefore introductions on those protocols and how they are connected to the full picture is given. The actual analysis on the impact of the floor control server into the Mp reference point is concluded in relation to the locations, giving basic flows, requirements analysis including a limited implementation proposal on supporting protocol parameters. The overall conclusion of the thesis is that even if both choices are seemingly useful, not one of the locations is clearly the most suitable in the light of this work. The thesis suggests a solution having both possibilities available to be chosen from in separate circumstances, realized with consistent standardization. It is evident, that if the preliminary assumption for the analysis is kept regarding to only one right place for the floor control server, more work is to be done in connected areas to discover the one most appropriate location.

Geant4 Hadronic Cascade Models and CMS Data Analysis : Computational Challenges in the LHC era

This work belongs to the field of computational high-energy physics (HEP). The key methods used in this thesis work to meet the challenges raised by the Large Hadron Collider (LHC) era experiments are object-orientation with software engineering, Monte Carlo simulation, the computer technology of clusters, and artificial neural networks. The first aspect discussed is the development of hadronic cascade models, used for the accurate simulation of medium-energy hadron-nucleus reactions, up to 10 GeV. These models are typically needed in hadronic calorimeter studies and in the estimation of radiation backgrounds. Various applications outside HEP include the medical field (such as hadron treatment simulations), space science (satellite shielding), and nuclear physics (spallation studies). Validation results are presented for several significant improvements released in Geant4 simulation tool, and the significance of the new models for computing in the Large Hadron Collider era is estimated. In particular, we estimate the ability of the Bertini cascade to simulate Compact Muon Solenoid (CMS) hadron calorimeter HCAL. LHC test beam activity has a tightly coupled cycle of simulation-to-data analysis. Typically, a Geant4 computer experiment is used to understand test beam measurements. Thus an another aspect of this thesis is a description of studies related to developing new CMS H2 test beam data analysis tools and performing data analysis on the basis of CMS Monte Carlo events. These events have been simulated in detail using Geant4 physics models, full CMS detector description, and event reconstruction. Using the ROOT data analysis framework we have developed an offline ANN-based approach to tag b-jets associated with heavy neutral Higgs particles, and we show that this kind of NN methodology can be successfully used to separate the Higgs signal from the background in the CMS experiment.

Theoretical Studies on Coupled Electron and Proton Transfer in Cytochrome c Oxidase

The complexity of life is based on an effective energy transduction machinery, which has evolved during the last 3.5 billion years. In aerobic life, the utilization of the high oxidizing potential of molecular oxygen powers this machinery. Oxygen is safely reduced by a membrane bound enzyme, cytochrome c oxidase (CcO), to produce an electrochemical proton gradient over the mitochondrial or bacterial membrane. This gradient is used for energy-requiring reactions such as synthesis of ATP by F0F1-ATPase and active transport. In this thesis, the molecular mechanism by which CcO couples the oxygen reduction chemistry to proton-pumping has been studied by theoretical computer simulations. By building both classical and quantum mechanical model systems based on the X-ray structure of CcO from Bos taurus, the dynamics and energetics of the system were studied in different intermediate states of the enzyme. As a result of this work, a mechanism was suggested by which CcO can prevent protons from leaking backwards in proton-pumping. The use and activation of two proton conducting channels were also enlightened together with a mechanism by which CcO sorts the chemical protons from pumped protons. The latter problem is referred to as the gating mechanism of CcO, and has remained a challenge in the bioenergetics field for more than three decades. Furthermore, a new method for deriving charge parameters for classical simulations of complex metalloenzymes was developed.

Proton translocation coupled to electron transfer reactions in terminal oxidases

Terminal oxidases are the final proteins of the respiratory chain in eukaryotes and some bacteria. They catalyze most of the biological oxygen consumption on Earth done by aerobic organisms. During the catalytic reaction terminal oxidases reduce dioxygen to water and use the energy released in this process to maintain the electrochemical proton gradient by functioning as a redox-driven proton pump. This membrane gradient of protons is extremely important for cells as it is used for many cellular processes, such as transportation of substrates and ATP synthesis. Even though the structures of several terminal oxidases are known, they are not sufficient in themselves to explain the molecular mechanism of proton pumping. In this work we have applied a complex approach using a variety of different techniques to address the properties and the mechanism of proton translocation by the terminal oxidases. The combination of direct measurements of pH changes during catalytic turnover, time-resolved potentiometric electrometry and optical spectroscopy, made it possible to obtain valuable information about various aspects of oxidase functioning. We compared oxygen binding properties of terminal oxidases from the distinct heme-copper (CcO) and cytochrome bd families and found that cytochrome bd has a high affinity for oxygen, which is 3 orders of magnitude higher than that of CcO. Interestingly, the difference between CcO and cytochrome bd is not only in higher affinity of the latter to oxygen, but also in the way that each of these enzymes traps oxygen during catalysis. CcO traps oxygen kinetically - the molecule of bound dioxygen is rapidly reduced before it can dissociate. Alternatively, cytochrome bd employs an alternative mechanism of oxygen trapping - part of the redox energy is invested into tight oxygen binding, and the price paid for this is the lack of proton pumping. A single cycle of oxygen reduction to water is characterized by translocation of four protons across the membrane. Our results make it possible to assign the pumping steps to discrete transitions of the catalytic cycle and indicate that during in vivo turnover of the oxidase these four protons are transferred, one at a time, during the P→F, F→OH, Oh→Eh, and Eh→R transitions. At the same time, each individual proton translocation step in the catalytic cycle is not just a single reaction catalyzed by CcO, but rather a complicated sequence of interdependent electron and proton transfers. We assume that each single proton translocation cycle of CcO is assured by internal proton transfer from the conserved Glu-278 to an as yet unidentified pump site above the hemes. Delivery of a proton to the pump site serves as a driving reaction that forces the proton translocation cycle to continue.

The viral coat protein is regulated by HSP70 and HSP40 in Potato virus A infection

Plus-stranded (plus) RNA viruses multiply within a cellular environment as tightly integrated units and rely on the genetic information carried within their genomes for multiplication and, hence, persistence. The minimal genomes of plus RNA viruses are unable to encode the molecular machineries that are required for virus multiplication. This sets requisites for the virus, which must form compatible interactions with host components during multiplication to successfully utilize primary metabolites as building blocks or metabolic energy, and to divert the protein synthesis machinery for production of viral proteins. In fact, the emerging picture of a virus-infected cell displays tight integration with the virus, from simple host and virus protein interactions through to major changes in the physiological state of the host cell. This study set out to develop a method for the identification of host components, mainly host proteins, that interact with proteins of Potato virus A (PVA; Potyvirus) during infection. This goal was approached by developing affinity-tag based methods for the purification of viral proteins complexed with associated host proteins from infected plants. Using this method, host membrane-associated viral ribonucleoprotein (RNP) complexes were obtained, and several host and viral proteins could be identified as components of these complexes. One of the host proteins identified using this strategy was a member of the heat shock protein 70 (HSP70) family, and this protein was chosen for further analysis. To enable the analysis of viral gene expression, a second method was developed based on Agrobacterium-mediated virus genome delivery into plant cells, and detection of virally expressed Renilla luciferase (RLUC) as a quantitative measure of viral gene expression. Using this method, it was observed that down-regulation of HSP70 caused a PVA coat protein (CP)-mediated defect associated with replication. Further experimentation suggested that CP can inhibit viral gene expression and that a distinct translational activity coupled to replication, referred to as replication-associated translation (RAT), exists. Unlike translation of replication-deficient viral RNA, RAT was dependent on HSP70 and its co-chaperone CPIP. HSP70 and CPIP together regulated CP turnover by promoting its modification by ubiquitin. Based on these results, an HSP70 and CPIP-driven mechanism that functions to regulate CP during viral RNA replication and/or translation is proposed, possibly to prevent premature particle assembly caused by CP association with viral RNA.

Dynamics of free-running, pump-modulated and coupled semiconductor and solid-state lasers

The output of a laser is a high frequency propagating electromagnetic field with superior coherence and brightness compared to that emitted by thermal sources. A multitude of different types of lasers exist, which also translates into large differences in the properties of their output. Moreover, the characteristics of the electromagnetic field emitted by a laser can be influenced from the outside, e.g., by injecting an external optical field or by optical feedback. In the case of free-running solitary class-B lasers, such as semiconductor and Nd:YVO4 solid-state lasers, the phase space is two-dimensional, the dynamical variables being the population inversion and the amplitude of the electromagnetic field. The two-dimensional structure of the phase space means that no complex dynamics can be found. If a class-B laser is perturbed from its steady state, then the steady state is restored after a short transient. However, as discussed in part (i) of this Thesis, the static properties of class-B lasers, as well as their artificially or noise induced dynamics around the steady state, can be experimentally studied in order to gain insight on laser behaviour, and to determine model parameters that are not known ab initio. In this Thesis particular attention is given to the linewidth enhancement factor, which describes the coupling between the gain and the refractive index in the active material. A highly desirable attribute of an oscillator is stability, both in frequency and amplitude. Nowadays, however, instabilities in coupled lasers have become an active area of research motivated not only by the interesting complex nonlinear dynamics but also by potential applications. In part (ii) of this Thesis the complex dynamics of unidirectionally coupled, i.e., optically injected, class-B lasers is investigated. An injected optical field increases the dimensionality of the phase space to three by turning the phase of the electromagnetic field into an important variable. This has a radical effect on laser behaviour, since very complex dynamics, including chaos, can be found in a nonlinear system with three degrees of freedom. The output of the injected laser can be controlled in experiments by varying the injection rate and the frequency of the injected light. In this Thesis the dynamics of unidirectionally coupled semiconductor and Nd:YVO4 solid-state lasers is studied numerically and experimentally.

Characterizing Physical Properties of Wetting Paper by Air Coupled Ultrasound and Light

This thesis reports investigations into the paper wetting process and its effects on the surface roughness and the out-of-plane (ZD) stiffness of machine-made paper. The aim of this work was to test the feasibility of employing air-borne ultrasound methods to determine surface roughness (by reflection) and ZD stiffness (by through transmission) of paper during penetration of distilled water, isopropanol and their mixtures. Air-borne ultrasound provides a non-contacting way to evaluate sample structure and mechanics during the liquid penetration event. Contrary to liquid immersion techniques, an air-borne measurement allows studying partial wetting of paper. In addition, two optical methods were developed to reveal the liquid location in paper during wetting. The laser light through transmission method was developed to monitor the liquid location in partially wetted paper. The white light reflection method was primarily used to monitor the penetration of the liquid front in the thickness direction. In the latter experiment the paper was fully wetted. The main results of the thesis were: 1) Liquid penetration induced surface roughening was quantified by monitoring the ultrasound reflection from the paper surface. 2) Liquid penetration induced stiffness alteration in the ZD of paper could be followed by measuring the change in the ultrasound ZD resonance in paper. 3) Through transmitted light revealed the liquid location in the partially wetted paper. 4) Liquid movement in the ZD of the paper could be observed by light reflection. The results imply that the presented ultrasonic means can without contact measure the alteration of paper roughness and stiffness during liquid transport. These methods can help avoiding over engineering the paper which reduces raw material and energy consumption in paper manufacturing. The presented optical means can estimate paper specific wetting properties, such as liquid penetration speed, transport mechanisms and liquid location within the paper structure. In process monitoring, these methods allow process tuning and manufacturing of paper with engineered liquid transport characteristics. With such knowledge the paper behaviour during printing can be predicted. These findings provide new methods for paper printing, surface sizing, and paper coating research.