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

Kidney Induction: control by Notch, Wnt and GDNF/Ret signalling

The permanent mammalian kidney (metanephros) develops as a result of complex reciprocal tissue interactions between a ureteric epithelium and the renal mesenchyme. The overall goal of the research in this thesis was to gain data that will eventually help in elucidating the formation of congenital renal malformations. The experiments in my thesis aimed to reveal the mechanisms by which Notch, Wnt and GDNF/Ret signalling pathways regulate the development of functional kidney. The function of Notch pathway was studied by a transgenic mouse model, where it was shown that overactivation of Notch signalling disturbs kidney development and alters the expression of Gdnf and Ret/GFRa1. This indicates that Notch signalling interplays with GDNF/Ret in the regulation of the primary ureteric budding and its subsequent branching. The data also suggested that strict spatio-temporal regulation of these two pathways is required for determination of ureteric tip-identity, which appeared to be crucial for the branch formation. The function of Wnt signalling in the ureteric morphogenesis was studied by in vivo and in vitro methods to show that a canonical pathway is required for ureteric branching. Stabilisation and deletion of the canonical pathway mediator, b-catenin specifically in the ureteric epithelium result in renal aplasia/hypodysplasia. These defects originate from severe blockage of ureteric branching due to the disrupted Ret signalling. Consequently, ureteric tip specific markers are lost and ureteric stalk identity is expanded throughout the whole epithelium. Thus, the data demonstrates that the Wnt/b-catenin pathway plays an essential role in the patterning and branching of the ureteric epithelium. A novel in vitro method was generated and utilised in nephron induction studies to reveal the mechanisms through which nephrogenesis is induced. Transient GSK3 inhibition results in stabilisation of b-catenin in the isolated renal mesenchyme, which efficiently triggers nephron formation. Also genetic stabilisation of b-catenin specifically in the mesenchyme results in spontaneous nephrogenesis. The results show that activation of the canonical Wnt pathway is sufficient to initiate nephrogenesis, and suggest that this pathway mediates the nephron induction in murine kidney mesenchymes. Taken together, this thesis demonstrates Notch and Wnt signalling pathways as novel regulators of ureteric branching morphogenesis, and that activation of the canonical Wnt pathway is sufficient for nephron induction. The studies also indicate that the Notch and Wnt pathways cross-talk with GDNF/Ret signalling in the patterning of ureteric epithelium.

Lactic acid bacteria and their antimicrobial peptides : Induction,detection,partial characterization, and potential applications

Bacteriocin-producing lactic acid bacteria and their isolated peptide bacteriocins are of value to control pathogens and spoiling microorganisms in foods and feed. Nisin is the only bacteriocin that is commonly accepted as a food preservative and has a broad spectrum of activity against Gram-positive organisms including spore forming bacteria. In this study nisin induction was studied from two perspectives, induction from inside of the cell and selection of nisin inducible strains with increased nisin induction sensitivity. The results showed that a mutation in the nisin precursor transporter NisT rendered L. lactis incapable of nisin secretion and lead to nisin accumulation inside the cells. Intracellular proteolytic activity could cleave the N-terminal leader peptide of nisin precursor, resulting in active nisin in the cells. Using a nisin sensitive GFP bioassay it could be shown, that the active intracellular nisin could function as an inducer without any detectable release from the cells. The results suggested that nisin can be inserted into the cytoplasmic membrane from inside the cell and activate NisK. This model of two-component regulation may be a general mechanism of how amphiphilic signals activate the histidine kinase sensor and would represent a novel way for a signal transduction pathway to recognize its signal. In addition, nisin induction was studied through the isolation of natural mutants of the GFPuv nisin bioassay strain L. lactis LAC275 using fl uorescence-activated cell sorting (FACS). The isolated mutant strains represent second generation of GFPuv bioassay strains which can allow the detection of nisin at lower levels. The applied aspect of this thesis was focused on the potential of bacteriocins in chicken farming. One aim was to study nisin as a potential growth promoter in chicken feed. Therefore, the lactic acid bacteria of chicken crop and the nisin sensitivity of the isolated strains were tested. It was found that in the crop Lactobacillus reuteri, L. salivarius and L. crispatus were the dominating bacteria and variation in nisin resistance level of these strains was found. This suggested that nisin may be used as growth promoter without wiping out the dominating bacterial species in the crop. As the isolated lactobacilli may serve as bacteria promoting chicken health or reducing zoonoosis and bacteriocin production is one property associated with probiotics, the isolated strains were screened for bacteriocin activity against the pathogen Campylobacter jejuni. The results showed that many of the isolated L. salivarius strains could inhibit the growth of C. jejuni. The bacteriocin of the L. salivarius LAB47 strain, with the strongest activity, was further characterized. Salivaricin 47 is heat-stable and active in pH range 3 to 8, and the molecular mass was estimated to be approximately 3.2 kDa based on tricine SDS-PAGE analysis.

Preparation of Industrially Important Hydroxy Acids and Diacids from 2,2-Disubstituted Propane-1,3-Diols and Linear Primary Diols by Green Chemistry Methods

Environmentally benign and economical methods for the preparation of industrially important hydroxy acids and diacids were developed. The carboxylic acids, used in polyesters, alkyd resins, and polyamides, were obtained by the oxidation of the corresponding alcohols with hydrogen peroxide or air catalyzed by sodium tungstate or supported noble metals. These oxidations were carried out using water as a solvent. The alcohols are also a useful alternative to the conventional reactants, hydroxyaldehydes and cycloalkanes. The oxidation of 2,2-disubstituted propane-1,3-diols with hydrogen peroxide catalyzed by sodium tungstate afforded 2,2-disubstituted 3-hydroxypropanoic acids and 1,1-disubstituted ethane-1,2-diols as products. A computational study of the Baeyer-Villiger rearrangement of the intermediate 2,2-disubstituted 3-hydroxypropanals gave in-depth data of the mechanism of the reaction. Linear primary diols having chain length of at least six carbons were easily oxidized with hydrogen peroxide to linear dicarboxylic acids catalyzed by sodium tungstate. The Pt/C catalyzed air oxidation of 2,2-disubstituted propane-1,3-diols and linear primary diols afforded the highest yield of the corresponding hydroxy acids, while the Pt, Bi/C catalyzed oxidation of the diols afforded the highest yield of the corresponding diacids. The mechanism of the promoted oxidation was best described by the ensemble effect, and by the formation of a complex of the hydroxy and the carboxy groups of the hydroxy acids with bismuth atoms. The Pt, Bi/C catalyzed air oxidation of 2-substituted 2-hydroxymethylpropane-1,3-diols gave 2-substituted malonic acids by the decarboxylation of the corresponding triacids. Activated carbon was the best support and bismuth the most efficient promoter in the air oxidation of 2,2-dialkylpropane-1,3-diols to diacids. In oxidations carried out in organic solvents barium sulfate could be a valuable alternative to activated carbon as a non-flammable support. In the Pt/C catalyzed air oxidation of 2,2-disubstituted propane-1,3-diols to 2,2-disubstituted 3-hydroxypropanoic acids the small size of the 2-substituents enhanced the rate of the oxidation. When the potential of platinum of the catalyst was not controlled, the highest yield of the diacids in the Pt, Bi/C catalyzed air oxidation of 2,2-dialkylpropane-1,3-diols was obtained in the regime of mass transfer. The most favorable pH of the reaction mixture of the promoted oxidation was 10. The reaction temperature of 40°C prevented the decarboxylation of the diacids.

On linear order and computation : The expressiveness of interactive computations on linear orders and computations indexed by ordinals

We solve the Dynamic Ehrenfeucht-Fra\"iss\'e Game on linear orders for both players, yielding a normal form for quantifier-rank equivalence classes of linear orders in first-order logic, infinitary logic, and generalized-infinitary logics with linearly ordered clocks. We show that Scott Sentences can be manipulated quickly, classified into local information, and consistency can be decided effectively in the length of the Scott Sentence. We describe a finite set of linked automata moving continuously on a linear order. Running them on ordinals, we compute the ordinal truth predicate and compute truth in the constructible universe of set-theory. Among the corollaries are a study of semi-models as efficient database of both model-theoretic and formulaic information, and a new proof of the atomicity of the Boolean algebra of sentences consistent with the theory of linear order -- i.e., that the finitely axiomatized theories of linear order are dense.

Regulation of Kinin receptor Expression in Heart Failure with a Focus on Vascular Endothelium

Accumulating evidence show that kinins, notably bradykinin (BK) and kallidin, have cardioprotective effects. To these include reduction of left ventricular hypertrophy (LVH) and progression of heart failure. The effects are mediated through two G protein-coupled receptors- bradykinin type-2 receptor (BK-2R) and bradykinin type -1 receptor (BK-1R). The widely accepted cardioprotective effects of BK-receptors relate to triggering the production and release of vasodilating nitric oxide (NO) by endothelial cells. They also exert anti-proliferative effects on fibroblasts and anti-hypertrophic effects on myocytes, and thus may play an essential role in the cardioprotective response to myocardial injury. The role for BK-1Rs in HF is based on experimental animal models, where the receptors have been linked to cardioprotective- but also to cardiotoxic -effects. The BK-1Rs are induced under inflammatory and ischemic conditions, shown in animal models; no previous reports, concerning BK-1Rs in human heart failure, have been presented. The expression of BK-2Rs is down-regulated in human end-stage heart failure. Present results showed that, in these patients, the BK-1Rs were up-regulated, suggesting that also BK-1Rs are involved in the pathogenesis of human heart failure. The receptors were localized mainly in the endothelium of intramyocardial coronary vessels, and correlated with the increased TNF-α expression in the myocardial coronary vessels. Moreover, in cultured endothelial cells, TNF-α was a potent trigger of BK-1Rs. These results suggest that cytokines may be responsible for the up-regulation of BK-1Rs in human heart failure. A linear relationship between BK-2R mRNA and protein expression in normal and failing human left ventricles implies that the BK-2Rs are regulated on the transcriptional level, at least in human myocardium. The expression of BK-2Rs correlated positively with age in normal and dilated hearts (IDC). The results suggest that human hearts adapts to age-related changes, by up-regulating the expression of cardioprotective BK-2Rs. Also, in the BK-2R promoter polymorphism -58 T/C, the C-allele was accumulated in cardiomyopathy patients which may partially explain the reduced number of BK-2Rs. Statins reduce the level of plasma cholesterol, but also exert several non-cholesterol-dependent effects. These effects were studied in human coronary arterial endothelial cells (hCAEC) and incubation with lovastatin induced both BK-1 and BK-2Rs in a time and concentration-dependent way. The induced BK-2Rs were functionally active, thus NO production and cGMP signaling was increased. Induction was abrogated by mevalonate, a direct HMG-CoA metabolite. Lovastatin is known to inhibit Rho activation, and by a selective RhoA kinase inhibitor (Y27632), a similar induction of BK-2R expression as with lovastatin. Interestingly a COX-2-inhibitor (NS398) inhibited this lovastatin-induction of BK-2Rs, suggesting that COX-2 inhibitors may affect the endothelial BK-2Rs, in a negative fashion. Hypoxia is a common denominator in HF but also in other cardiovascular diseases. An induction of BK-2Rs in mild hypoxic conditions was shown in cultured hCAECs, which was abolished by a specific BK-2R inhibitor Icatibant. These receptors were functionally active, thus BK increased and Icatibant inhibited the production of NO. In rat myocardium the expression of BK-2R was increased in the endothelium of vessels, forming at the border zone, between the scar tissue and the healthy myocardium. Moreover, in in vitro wound-healing assay, endothelial cells were cultured under hypoxic conditions and BK significantly increased the migration of these cells and as Icatibant inhibited it. These results show, that mild hypoxia triggers a temporal expression of functionally active BK-2Rs in human and rat endothelial cells, supporting a role for BK-2Rs, in hypoxia induced angiogenesis. Our and previous results show, that BK-Rs have an impact on the cardiovascular diseases. In humans, at the end stage of heart failure, the BK-2Rs are down-regulated and BK-1Rs induced. Whether the up-regulation of BK-1Rs, is a compensatory mechanism against the down-regulation of BK-2Rs, or merely reflects the end point of heart failure, remains to bee seen. In a clinical point of view, the up-regulation of BK-2Rs, under hypoxic conditions or statin treatment, suggests that, the induction of BK-2Rs is protective in cardiovascular pathologies and those treatments activating BK-2Rs, might give additional tools in treating heart failure.

Growth factor induction in intervertebral disc tissue: Observations in basic mechanisms of disc degeneration and rearrangement

The intervertebral disc is composed of concentrically arranged components: annulus fibrosus, the transition zone, and central nucleus pulposus. The major disc cell type differs in various parts of the intervertebral disc. In annulus fibrosus a spindle shaped fibroblast-like cell mainly dominates, whereas in central nucleus pulposus the more rounded chondrocyte-like disc cell is the major cell type. At birth the intervertebral disc is well vascularized, but during childhood and adolescence blood vessels become smaller and less numerous. The adult intervertebral disc is avascular and is nourished via the cartilage endplates. On the other hand, degenerated and prolapsed intervertebral discs are again vascularized, and show many changes compared to normal discs, including: nerve ingrowth, change in collagen turnover, and change in water content. Furthermore, the prolapsed intervertebral disc tissue has a tendency to decrease in size over time. Growth factors are polypeptides which regulate cell growth, extracellular matrix protease activity, and vascularization. Oncoproteins c-Fos and c-Jun heterodimerize, forming the AP-1 transcription factor which is expressed in activated cells. In this thesis the differences of growth factor expression in normal intervertebral disc, the degenerated intervertebral disc and herniated intervertebral disc were analyzed. Growth factors of particular interest were basic fibroblast growth factor (bFGF or FGF-2), platelet-derived growth factor (PDGF), vascular endothelial growth factor (VEGF), and transforming growth factor beta (TGFβ). Cell activation was visualized by the expression of the AP-1 transcription promoters c-Fos and c-Jun. The expression was shown with either mono- or polyclonal antibodies by indirect avidin-biotin-peroxidase immunohistochemical staining method. The normal control material was collected from a tissue bank of five organ donors. The degenerated disc material was from twelve patients operated on for painful degenerative disc disease, and herniated disc tissue material was obtained from 115 patients operated on for sciatica. Normal control discs showed only TGFβ immunopositivity. All other factors studied were immunonegative in the control material. Prolapsed disc material was immunopositive for all factors studied, and this positivity was located either in the disc cells or in blood vessels. Furthermore, neovascularization was noted. Disc cell immunoreaction was shown in chondrocyte-like disc cells or in fibroblast-like disc cells, the former being expressed especially in conglomerates (clusters of disc cells). TGFβ receptor induction was prominent in prolapsed intervertebral disc tissue. In degenerated disc material, the expression of growth factors was analyzed in greater detail in various parts of the disc: nucleus pulposus, anterior annulus fibrosus and posterior annulus fibrosus. PDGF did not show any immunoreactivity, whereas all other studied growth factors were localized either in chondrocyte-like disc cells, often forming clusters, in fibroblast-like disc cells, or in small capillaries. Many of the studied degenerated discs showed tears in the posterior region of annulus fibrosus, but expression of immunopositive growth factors was detected throughout the entire disc. Furthermore, there was a difference in immunopositive cell types for different growth factors. The main conclusion of the thesis, supported by all substudies, is the occurrence of growth factors in disc cells. They may be actively participating in a network regulating disc cell growth, proliferation, extracellular matrix turnover, and neovascularization. Chondrocyte-like disc cells, in particular, expressed growth factors and oncoproteins, highlighting the importance of this cell type in the basic pathophysiologic events involved in disc degeneration and disc rearrangement. The thesis proposes a hypothesis for cellular remodelling in intervertebral disc tissue. In summary, the model presents an activation pattern of different growth factors at different intervertebral disc stages, mechanisms leading to neovascularization of the intervertebral disc in pathological conditions, and alteration of disc cell shape, especially in annulus fibrosus. Chondrocyte-like disc cells become more numerous, and these cells are capable of forming clusters, which appear to be regionally active within the disc. The alteration of the phenotype of disc cells expressing growth factors from fibroblast-like disc cells to chondrocyte-like cells in annulus fibrosus, and the numerous expression of growth factor expressing disc cells in nucleus pulposus, may be a key element both during pathological degeneration of the intervertebral disc, and during the healing process after trauma.

Theoretical modeling of ionospheric electrodynamics including induction effects

This thesis deals with theoretical modeling of the electrodynamics of auroral ionospheres. In the five research articles forming the main part of the thesis we have concentrated on two main themes: Development of new data-analysis techniques and study of inductive phenomena in the ionospheric electrodynamics. The introductory part of the thesis provides a background for these new results and places them in the wider context of ionospheric research. In this thesis we have developed a new tool (called 1D SECS) for analysing ground based magnetic measurements from a 1-dimensional magnetometer chain (usually aligned in the North-South direction) and a new method for obtaining ionospheric electric field from combined ground based magnetic measurements and estimated ionospheric electric conductance. Both these methods are based on earlier work, but contain important new features: 1D SECS respects the spherical geometry of large scale ionospheric electrojet systems and due to an innovative way of implementing boundary conditions the new method for obtaining electric fields can be applied also at local scale studies. These new calculation methods have been tested using both simulated and real data. The tests indicate that the new methods are more reliable than the previous techniques. Inductive phenomena are intimately related to temporal changes in electric currents. As the large scale ionospheric current systems change relatively slowly, in time scales of several minutes or hours, inductive effects are usually assumed to be negligible. However, during the past ten years, it has been realised that induction can play an important part in some ionospheric phenomena. In this thesis we have studied the role of inductive electric fields and currents in ionospheric electrodynamics. We have formulated the induction problem so that only ionospheric electric parameters are used in the calculations. This is in contrast to previous studies, which require knowledge of the magnetospheric-ionosphere coupling. We have applied our technique to several realistic models of typical auroral phenomena. The results indicate that inductive electric fields and currents are locally important during the most dynamical phenomena (like the westward travelling surge, WTS). In these situations induction may locally contribute up to 20-30% of the total ionospheric electric field and currents. Inductive phenomena do also change the field-aligned currents flowing between the ionosphere and magnetosphere, thus modifying the coupling between the two regions.