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

Rhetoric and Representation : Exploring the Cultural Meaning of the Natural Sciences in Contemporary Popular Science Writing and Literature

Kirjallisuuden- ja kulttuurintutkimus on viimeisten kolmen vuosikymmenen aikana tullut yhä enenevässä määrin tietoiseksi tieteen ja taiteen suhteen monimutkaisesta luonteesta. Nykyään näiden kahden kulttuurin tutkimus muodostaa oman kenttänsä, jolla niiden suhdetta tarkastellaan ennen kaikkea dynaamisena vuorovaikutuksena, joka heijastaa kulttuurimme kieltä, arvoja ja ideologisia sisältöjä. Toisin kuin aiemmat näkemykset, jotka pitävät tiedettä ja taidetta toisilleen enemmän tai vähemmän vastakkaisina pyrkimyksinä, nykytutkimus lähtee oletuksesta, jonka mukaan ne ovat kulttuurillisesti rakentuneita diskursseja, jotka kohtaavat usein samankaltaisia todellisuuden mallintamiseen liittyviä ongelmia, vaikka niiden käyttämät metodit eroavatkin toisistaan. Väitöskirjani keskittyy yllä mainitun suhteen osa-alueista popularisoidun tietokirjallisuuden (muun muassa Paul Davies, James Gleick ja Richard Dawkins) käyttämän kielen ja luonnontieteistä ideoita ammentavan kaunokirjallisuuden (muun muassa Jeanette Winterson, Tom Stoppard ja Richard Powers) hyödyntämien keinojen tarkasteluun nojautuen yli 30 teoksen kattavaa aineistoa koskevaan tyylin ja teemojen tekstianalyysiin. Populaarin tietokirjallisuuden osalta tarkoituksenani on osoittaa, että sen käyttämä kieli rakentuu huomattavassa määrin sellaisille rakenteille, jotka tarjoavat mahdollisuuden esittää todellisuutta koskevia argumentteja mahdollisimman vakuuttavalla tavalla. Tässä tehtävässä monilla klassisen retoriikan määrittelemillä kuvioilla on tärkeä rooli, koska ne auttavat liittämään sanotun sisällön ja muodon tiukasti toisiinsa: retoristen kuvioiden käyttö ei näin ollen edusta pelkkää tyylikeinoa, vaan se myös usein kiteyttää argumenttien taustalla olevat tieteenfilosofiset olettamukset ja auttaa vakiinnuttamaan argumentoinnin logiikan. Koska monet aikaisemmin ilmestyneistä tutkimuksista ovat keskittyneet pelkästään metaforan rooliin tieteellisissä argumenteissa, tämä väitöskirja pyrkii laajentamaan tutkimuskenttää analysoimalla myös toisenlaisten kuvioiden käyttöä. Osoitan myös, että retoristen kuvioiden käyttö muodostaa yhtymäkohdan tieteellisiä ideoita hyödyntävään kaunokirjallisuuteen. Siinä missä popularisoitu tiede käyttää retoriikkaa vahvistaakseen sekä argumentatiivisia että kaunokirjallisia ominaisuuksiaan, kuvaa tällainen sanataide tiedettä tavoilla, jotka usein heijastelevat tietokirjallisuuden kielellisiä rakenteita. Toisaalta on myös mahdollista nähdä, miten kaunokirjallisuuden keinot heijastuvat popularisoidun tieteen kerrontatapoihin ja kieleen todistaen kahden kulttuurin dynaamisesta vuorovaikutuksesta. Nykyaikaisen populaaritieteen retoristen elementtien ja kaunokirjallisuuden keinojen vertailu näyttää lisäksi, kuinka tiede ja taide osallistuvat keskusteluun kulttuurimme tiettyjen peruskäsitteiden kuten identiteetin, tiedon ja ajan merkityksestä. Tällä tavoin on mahdollista nähdä, että molemmat ovat perustavanlaatuisia osia merkityksenantoprosessissa, jonka kautta niin tieteelliset ideat kuin ihmiselämän suuret kysymyksetkin saavat kulttuurillisesti rakentuneen merkityksensä.

Toward Figural Fantasy : The Representation of Consciousness in Modern American Fantasy Literature

Tajunnanesitys amerikkalaisessa heterodiegeettisessä fantasiakirjallisuudessa on muuttunut merkittävästi viimeisen kolmen vuosikymmenen aikana: kerrontaa orientoiva ja tarinamaailmaa havainnoiva tajunta on vähin erin vaihtunut kaikkitietävästä kertojasta tarinan sisäiseksi henkilöhahmoksi. Kertoja on samalla vetäytynyt yhä syvemmälle kerronnan kulissien taakse. Tämä tutkielma hahmottaa ja analysoi kyseistä muutosta siirtymänä kertojakeskeisestä kerronnasta kohti henkilökeskeistä kerrontaa. Tutkielmassa tajunnanesityksen teoreettisen kehyksen muodostavat F. K. Stanzelin kertojakeskeisen ja henkilökeskeisen kerrontatilanteen käsitteet. Kerrontatilanteita tarkennetaan fokalisaation, vapaan epäsuoran esityksen, sisäisen monologin ja psykonarraation teorioiden avulla. Tutkielma jakaantuu kahteen osaan. Ensimmäisessä osassa vertaillaan kahta prototyyppistä fantasiaromaania syväluotaavan narratologisen analyysin keinoin. Kertojakeskeistä kerrontaa edustaa Fritz Leiberin "The Swords of Lankhmar" (1968) ja henkilökeskeistä kerrontaa George R. R. Martinin "A Game of Thrones" (1996). Toisessa osassa tarkastellaan pääpiirteittäin kuuttatoista muuta aikaansa edustavaa fantasiaromaania ja hahmotetaan tajunnanesityksen muutoksen kronologista kulkua. Yhdessä osat ilmentävät, kuinka amerikkalainen heterodiegeettinen fantasiakirjallisuus on muuttunut kerrontateknisesti henkilökeskeisemmäksi. Tutkielma on ensimmäinen laatuaan, ja sen on tarkoitus luoda pohjaa uudenlaiselle modernin fantasiakirjallisuuden tutkimukselle ja kirjalliselle arvostukselle.

Concepts and Object-Oriented Knowledge Representation

Tutkielma käsittelee nykyisiä kognitiotieteen teorioita käsitteistä ja niiden mallintamista oliokeskeisillä tietämyksen esittämisen menetelmillä. Käsiteteorioista käsitellään klassinen, määritelmäteoria, prototyyppiteoria, duaaliteoriat, uusklassinen teoria, teoria-teoria ja atomistinen teoria. Oliokeskeiset menetelmät ovat viime aikoina jakautuneet kahden tyyppisiin kieliin: oliopohjaisiin ja luokkapohjaisiin. Uudet olio-pohjaiset olio-ohjelmointikielet antavat käsitteiden representointiin mahdollisuuksia, jotka puuttuvat aikaisemmista luokka-pohjaisista kielistä ja myös kehysmenetelmistä. Tutkielma osoittaa, että oliopohjaisten kielten uudet piirteet tarjoavat keinoja, joilla käsitteitä voidaan esittää symbolisessa muodossa paremmin kuin perinteisillä menetelmillä. Niillä pystytään simuloimaan kaikkea mitä luokkapohjaisilla kielillä voidaan, mutta ne pystyvät lisäksi simuloimaan perheyhtäläisyyskäsitteitä ja mahdollistavat olioiden dynaamisen muuttamisen ilman, että siinä rikotaan psykologisen essentialismin periaatetta. Tutkielma osoittaa lisäksi vakavia puutteitta, jotka koskevat koko oliokeskeistä menetelmää. Avainsanat: käsitteet, käsiteteoriat, tekoäly, komputationaalinen psykologia, olio-ohjelmointi, tiedon esittäminen

Stand structural dynamics on pristine and managed boreal peatlands

The objectives of this study were to investigate the stand structure and succession dynamics in Scots pine (Pinus sylvestris L.) stands on pristine peatlands and in Scots pine and Norway spruce (Picea abies (L.) Karst.) dominated stands on drained peatlands. Furthermore, my focus was on characterising how the inherent and environmental factors and the intermediate thinnings modify the stand structure and succession. For pristine peatlands, the study was based on inventorial stand data, while for drained peatlands, longitudinal data from repeatedly measured stands were utilised. The studied sites covered the most common peatland site types in Finland. They were classified into two categories according to the ecohydrological properties related to microsite variation and nutrient levels within sites. Tree DBH and age distributions in relation to climate and site type were used to study the stand dynamics on pristine sites. On drained sites, the Weibull function was used to parameterise the DBH distributions and mixed linear models were constructed to characterise the impacts of different ecological factors on stand dynamics. On pristine peatlands, both climate and the ecohydrology of the site proved to be crucial factors determining the stand structure and its dynamics. Irrespective of the vegetation succession, enhanced site productivity and increased stand stocking they significantly affected the stand dynamics also on drained sites. On the most stocked sites on pristine peatlands the inter-tree competition seemed to also be a significant factor modifying stand dynamics. Tree age and size diversity increased with stand age, but levelled out in the long term. After drainage, the stand structural unevenness increased due to the regeneration and/or ingrowth of the trees. This increase was more pronounced on sparsely forested composite sites than on more fully stocked genuine forested sites in Scots pine stands, which further undergo the formation of birch and spruce undergrowth beneath the overstory as succession proceeds. At 20-30 years after drainage the structural heterogeneity started to decrease, indicating increased inter-tree competition, which increased the mortality of suppressed trees within stand. Peatland stands are more dynamic than anticipated and are generally not characterized by a balanced, self-perpetuating structure. On pristine sites, various successional pathways are possible, whereas on drained sites the succession has more uniform trend. Typically, stand succession proceeds without any distinct developmental stages on pristine peatlands, whereas on drained peatlands, at least three distinct stages could be identified. Thinnings had only little impact on the stand succession. The new information on stand dynamics may be utilised, e.g. in forest management planning to facilitate the allocation of the growth resources to the desired crop component by appropriate silvicultural treatments, as well as assist in assessing the effects of the climate change on the forested boreal peatlands.

Biochemical and structural properties of Potato virus A VPg

The potato virus A (PVA) genome linked protein (VPg) is a multifunctional protein that takes part in vital infection cycle events such as replication and movement of the virus from cell to cell. VPg is attached to the 5´ end of the genome and is carried in the tip structure of the filamentous virus particle. VPg is also the last protein to be cleaved from the polyprotein. VPg interacts with several viral and host proteins and is phosphorylated at several positions. These features indicate a central role in virus epidemiology and a requirement for an efficient but flexible mechanism for switching between different functions. -- This study examines some of the key VPg functions in more detail. Mutations in the positively charged region from Ala38 to Lys44 affected the NTP binding, uridylylation, and in vitro translation inhibition activities of VPg, whereas in vivo translation inhibition was not affected. Some of the data generated in this study implicated the structural flexibility of the protein in functional activities. VPg lacks a rigid structure, which could allow it to adapt conformationally to different functions as needed. A major finding of this study is that PVA VPg belongs to the class of ´intrinsically disordered proteins´ (IDPs). IDPs are a novel protein class that has helped to explain the observed lack of structure. The existence of IDPs clearly shows that proteins can be functional and adapt a native fold without a rigid structure. Evidence for the intrinsic disorder of VPg was provided by CD spectroscopy, NMR, fluorescence spectroscopy, bioinformatic analysis, and limited proteolytic digestion. The structure of VPg resembles that of a molten globule-type protein and has a hydrophobic core domain. Approximately 50% of the protein is disordered and an α-helical stabilization of these regions has been hypothesized. Surprisingly, VPg structure was stabilized in the presence of anionic lipid vesicles. The stabilization was accompanied by a change in VPg structure and major morphological modifications of the vesicles, including a pronounced increase in the size and appearance of pore or plaque like formations on the vesicle surface. The most likely scenario seems to be an α-helical stabilization of VPg which induces formation of a pore or channel-like structure on the vesicle surface. The size increase is probably due to fusion or swelling of the vesicles. The latter hypothesis is supported by the evident disruption of the vesicles after prolonged incubation with VPg. A model describing the results is presented and discussed in relation to other known properties of the protein.

Structural analyses of (1->3),(1->4)-β-D-glucan of oats and barley

The structures of (1→3),(1→4)-β-D-glucans of oat bran, whole-grain oats and barley and processed foods were analysed. Various methods of hydrolysis of β-glucan, the content of insoluble fibre of whole grains of oats and barley and the solution behaviour of oat and barley β-glucans were studied. The isolated soluble β-glucans of oat bran and whole-grain oats and barley were hydrolysed with lichenase, an enzyme specific for (1→3),(1→4)-β-D-β-glucans. The amounts of oligosaccharides produced from bran were analysed with capillary electrophoresis and those from whole-grains with high-performance anion-exchange chromatography with pulse-amperometric detection. The main products were 3-O-β-cellobiosyl-D-glucose and 3-O-β-cellotriosyl-D-glucose, the oligosaccharides which have a degree of polymerisation denoted by DP3 and DP4. Small differences were detected between soluble and insoluble β-glucans and also between β-glucans of oats and barley. These differences can only be seen in the DP3:DP4 ratio which was higher for barley than for oat and also higher for insoluble than for soluble β-glucan. A greater proportion of barley β-glucan remained insoluble than of oat β-glucan. The molar masses of soluble β-glucans of oats and barley were the same as were those of insoluble β-glucans of oats and barley. To analyse the effects of cooking, baking, fermentation and drying, β-glucan was isolated from porridge, bread and fermentate and also from their starting materials. More β-glucan was released after cooking and less after baking. Drying decreased the extractability for bread and fermentate but increased it for porridge. Different hydrolysis methods of β-glucan were compared. Acid hydrolysis and the modified AOAC method gave similar results. The results of hydrolysis with lichenase gave higher recoveries than the other two. The combination of lichenase hydrolysis and high-performance anion-exchange chromatography with pulse-amperometric detection was found best for the analysis of β-glucan content. The content of insoluble fibre was higher for barley than for oats and the amount of β-glucan in the insoluble fibre fraction was higher for oats than for barley. The flow properties of both water and aqueous cuoxam solutions of oat and barley β-glucans were studied. Shear thinning was stronger for the water solutions of oat β-glucan than for barley β-glucan. In aqueous cuoxam shear thinning was not observed at the same concentration as in water but only with high concentration solutions. Then the viscosity of barley β-glucan was slightly higher than that of oat β-glucan. The oscillatory measurements showed that the crossover point of the G´ and G´´ curves was much lower for barley β-glucan than for oat β-glucan indicating a higher tendency towards solid-like behaviour for barley β-glucan than for oat β-glucan.

Preparation, structural analysis and prebiotic potential of arabinoxylo-oligosaccharides

Arabinoxylo-oligosaccharides (AXOS) can be prepared enzymatically from arabinoxylans (AX) and AXOS are known to possess prebiotic potential. Here the structural features of 10 cereal AX were examined. AX were hydrolysed by Shearzyme® to prepare AXOS, and their structures were fully analysed. The prebiotic potential of the purified AXOS was studied in the fermentation experiments with bifidobacteria and faecal microbiota. In AX extracted from flours and bran, high amounts of a-L-Araf units are attached to the b-D-Xylp main chain, whereas moderate or low degree of substitution was found from husks, cob and straw. Nuclear magnetic resonance (NMR) spectroscopy showed that flour and bran AX contain high amounts of a-L-Araf units bound to the O-3 of b-D-Xylp residues and doubly substituted b-D-Xylp units with a-L-Araf substituents at O-2 and O-3. Barley husk and corn cob AX contain high amounts of b-D-Xylp(1→2)-a-L-Araf(1→3) side chains, which can also be found in AX from oat spelts and rice husks, and in lesser amounts in wheat straw AX. Rye and wheat flour AX and oat spelt AX were hydrolysed by Shearzyme® (with Aspergillus aculeatus GH10 endo-1,4-b-D-xylanase as the main enzyme) for the production of AXOS on a milligram scale. The AXOS were purified and their structures fully analysed, using mass spectrometry (MS) and 1D and 2D NMR spectroscopy. Monosubstituted xylobiose and xylotriose with a-L-Araf attached to the O-3 or O-2 of the nonreducing end b-D-Xylp unit and disubstituted AXOS with two a-L-Araf units at the nonreducing end b-D-Xylp unit of xylobiose or xylotriose were produced. Xylobiose with b-D-Xylp(1→2)-a-L-Araf(1→3) side chain was also purified. These AXOS were used as standards in further identification and quantification of corresponding AXOS from the hydrolysates in high-performance anion-exchange chromatography with pulsed amperometric detection (HPAEC-PAD) analysis. The prebiotic potential of AXOS was tested in in vitro fermentation experiments. Bifidobacterium adolescentis ATCC 15703 and B. longum ATCC 15707 utilized AXOS from the AX hydrolysates. Both species released L-arabinose from AXOS, but B. adolescentis consumed the XOS formed, whereas B. longum fermented the L-arabinose released. The third species tested, B. breve ATCC 15700, grew poorly on these substrates. When cultivated on pure AXOS, the bifidobacterial mixture utilized pure singly substituted AXOS almost completely, but no growth was detected with pure doubly substituted AXOS as substrates. However, doubly substituted AXOS were utilized from the mixture of xylose, XOS and AXOS. Faecal microbiota utilized both pure singly and doubly substituted AXOS. Thus, a mixture of singly and doubly substituted AXOS could function as a suitable, slowly fermenting prebiotic substance. This thesis contributes to the structural information on cereal AX and preparation of mono and doubly substituted AXOS from AX. Understanding the utilization strategies is fundamental in evaluating the prebiotic potential of AXOS. Further research is still required before AXOS can be used in applications for human consumption.

Structural characteristics affecting functions of two actin regulating proteins

Structural biology is a branch of science that concentrates on the relationship between the structure and function of biological macromolecules. The prevalence of a large number of three dimensional structures offers effective tools for bio-scientists to understand the living world. Actin is the most abundant cellular protein and one of its main functions is to produce movement in living cells. Actin forms filaments that are dynamic and which are regulated by a number of different proteins. A class of these regulatory proteins contains actin depolymerizing factor homology (ADF-H) domains. These directly interact with actin through their ADF-H domains. Although ADF-H domains possess very similar three dimensional structures to one another, they vary in their functional properties. One example of this is the ability to bind to actin monomers or filaments. During the work for this thesis two structures of ADF-H domains were solved by nuclear magnetic resonance spectroscopy (NMR). The elucidated structures help us understand the binding specificities of the ADF-H family members.

Deriving structural information from non-coding ribonucleic acids by mass spectrometry

The purpose of this study is to describe the development of application of mass spectrometry for the structural analyses of non-coding ribonucleic acids during past decade. Mass spectrometric methods are compared of traditional gel electrophoretic methods, the characteristics of performance of mass spectrometric, analyses are studied and the future trends of mass spectrometry of ribonucleic acids are discussed. Non-coding ribonucleic acids are short polymeric biomolecules which are not translated to proteins, but which may affect the gene expression in all organisms. Regulatory ribonucleic acids act through transient interactions with key molecules in signal transduction pathways. Interactions are mediated through specific secondary and tertiary structures. Posttranscriptional modifications in the structures of molecules may introduce new properties to the organism, such as adaptation to environmental changes or development of resistance to antibiotics. In the scope of this study, the structural studies include i) determination of the sequence of nucleobases in the polymer chain, ii) characterisation and localisation of posttranscriptional modifications in nucleobases and in the backbone structure, iii) identification of ribonucleic acid-binding molecules and iv) probing of higher order structures in the ribonucleic acid molecule. Bacteria, archaea, viruses and HeLa cancer cells have been used as target organisms. Synthesised ribonucleic acids consisting of structural regions of interest have been frequently used. Electrospray ionisation (ESI) and matrix-assisted laser desorption ionisation (MALDI) have been used for ionisation of ribonucleic analytes. Ammonium acetate and 2-propanol are common solvents for ESI. Trihydroxyacetophenone is the optimal MALDI matrix for ionisation of ribonucleic acids and peptides. Ammonium salts are used in ESI buffers and MALDI matrices as additives to remove cation adducts. Reverse phase high performance liquid chromatography has been used for desalting and fractionation of analytes either off-line of on-line, coupled with ESI source. Triethylamine and triethylammonium bicarbonate are used as ion pair reagents almost exclusively. Fourier transform ion cyclotron resonance analyser using ESI coupled with liquid chromatography is the platform of choice for all forms of structural analyses. Time-of-flight (TOF) analyser using MALDI may offer sensitive, easy-to-use and economical solution for simple sequencing of longer oligonucleotides and analyses of analyte mixtures without prior fractionation. Special analysis software is used for computer-aided interpretation of mass spectra. With mass spectrometry, sequences of 20-30 nucleotides of length may be determined unambiguously. Sequencing may be applied to quality control of short synthetic oligomers for analytical purposes. Sequencing in conjunction with other structural studies enables accurate localisation and characterisation of posttranscriptional modifications and identification of nucleobases and amino acids at the sites of interaction. High throughput screening methods for RNA-binding ligands have been developed. Probing of the higher order structures has provided supportive data for computer-generated three dimensional models of viral pseudoknots. In conclusion. mass spectrometric methods are well suited for structural analyses of small species of ribonucleic acids, such as short non-coding ribonucleic acids in the molecular size region of 20-30 nucleotides. Structural information not attainable with other methods of analyses, such as nuclear magnetic resonance and X-ray crystallography, may be obtained with the use of mass spectrometry. Sequencing may be applied to quality control of short synthetic oligomers for analytical purposes. Ligand screening may be used in the search of possible new therapeutic agents. Demanding assay design and challenging interpretation of data requires multidisclipinary knowledge. The implement of mass spectrometry to structural studies of ribonucleic acids is probably most efficiently conducted in specialist groups consisting of researchers from various fields of science.