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

On the Origin of Ideas : An Abductivist Approach to Discovery

The purpose of this study is to analyze and develop various forms of abduction as a means of conceptualizing processes of discovery. Abduction was originally presented by Charles S. Peirce (1839-1914) as a "weak", third main mode of inference -- besides deduction and induction -- one which, he proposed, is closely related to many kinds of cognitive processes, such as instincts, perception, practices and mediated activity in general. Both abduction and discovery are controversial issues in philosophy of science. It is often claimed that discovery cannot be a proper subject area for conceptual analysis and, accordingly, abduction cannot serve as a "logic of discovery". I argue, however, that abduction gives essential means for understanding processes of discovery although it cannot give rise to a manual or algorithm for making discoveries. In the first part of the study, I briefly present how the main trend in philosophy of science has, for a long time, been critical towards a systematic account of discovery. Various models have, however, been suggested. I outline a short history of abduction; first Peirce's evolving forms of his theory, and then later developments. Although abduction has not been a major area of research until quite recently, I review some critiques of it and look at the ways it has been analyzed, developed and used in various fields of research. Peirce's own writings and later developments, I argue, leave room for various subsequent interpretations of abduction. The second part of the study consists of six research articles. First I treat "classical" arguments against abduction as a logic of discovery. I show that by developing strategic aspects of abductive inference these arguments can be countered. Nowadays the term 'abduction' is often used as a synonym for the Inference to the Best Explanation (IBE) model. I argue, however, that it is useful to distinguish between IBE ("Harmanian abduction") and "Hansonian abduction"; the latter concentrating on analyzing processes of discovery. The distinctions between loveliness and likeliness, and between potential and actual explanations are more fruitful within Hansonian abduction. I clarify the nature of abduction by using Peirce's distinction between three areas of "semeiotic": grammar, critic, and methodeutic. Grammar (emphasizing "Firstnesses" and iconicity) and methodeutic (i.e., a processual approach) especially, give new means for understanding abduction. Peirce himself held a controversial view that new abductive ideas are products of an instinct and an inference at the same time. I maintain that it is beneficial to make a clear distinction between abductive inference and abductive instinct, on the basis of which both can be developed further. Besides these, I analyze abduction as a part of distributed cognition which emphasizes a long-term interaction with the material, social and cultural environment as a source for abductive ideas. This approach suggests a "trialogical" model in which inquirers are fundamentally connected both to other inquirers and to the objects of inquiry. As for the classical Meno paradox about discovery, I show that abduction provides more than one answer. As my main example of abductive methodology, I analyze the process of Ignaz Semmelweis' research on childbed fever. A central basis for abduction is the claim that discovery is not a sequence of events governed only by processes of chance. Abduction treats those processes which both constrain and instigate the search for new ideas; starting from the use of clues as a starting point for discovery, but continuing in considerations like elegance and 'loveliness'. The study then continues a Peircean-Hansonian research programme by developing abduction as a way of analyzing processes of discovery.

Logic as the Universal Science : Bertrand Russell's Early Conception of Logic and Its Philosophical Context

Bertrand Russell (1872 1970) introduced the English-speaking philosophical world to modern, mathematical logic and foundational study of mathematics. The present study concerns the conception of logic that underlies his early logicist philosophy of mathematics, formulated in The Principles of Mathematics (1903). In 1967, Jean van Heijenoort published a paper, Logic as Language and Logic as Calculus, in which he argued that the early development of modern logic (roughly the period 1879 1930) can be understood, when considered in the light of a distinction between two essentially different perspectives on logic. According to the view of logic as language, logic constitutes the general framework for all rational discourse, or meaningful use of language, whereas the conception of logic as calculus regards logic more as a symbolism which is subject to reinterpretation. The calculus-view paves the way for systematic metatheory, where logic itself becomes a subject of mathematical study (model-theory). Several scholars have interpreted Russell s views on logic with the help of the interpretative tool introduced by van Heijenoort,. They have commonly argued that Russell s is a clear-cut case of the view of logic as language. In the present study a detailed reconstruction of the view and its implications is provided, and it is argued that the interpretation is seriously misleading as to what he really thought about logic. I argue that Russell s conception is best understood by setting it in its proper philosophical context. This is constituted by Immanuel Kant s theory of mathematics. Kant had argued that purely conceptual thought basically, the logical forms recognised in Aristotelian logic cannot capture the content of mathematical judgments and reasonings. Mathematical cognition is not grounded in logic but in space and time as the pure forms of intuition. As against this view, Russell argued that once logic is developed into a proper tool which can be applied to mathematical theories, Kant s views turn out to be completely wrong. In the present work the view is defended that Russell s logicist philosophy of mathematics, or the view that mathematics is really only logic, is based on what I term the Bolzanian account of logic . According to this conception, (i) the distinction between form and content is not explanatory in logic; (ii) the propositions of logic have genuine content; (iii) this content is conferred upon them by special entities, logical constants . The Bolzanian account, it is argued, is both historically important and throws genuine light on Russell s conception of logic.

Constructive Perspectives on Inductive Logic

Constructive (intuitionist, anti-realist) semantics has thus far been lacking an adequate concept of truth in infinity concerning factual (i.e., empirical, non-mathematical) sentences. One consequence of this problem is the difficulty of incorporating inductive reasoning in constructive semantics. It is not possible to formulate a notion for probable truth in infinity if there is no adequate notion of what truth in infinity is. One needs a notion of a constructive possible world based on sensory experience. Moreover, a constructive probability measure must be defined over these constructively possible empirical worlds. This study defines a particular kind of approach to the concept of truth in infinity for Rudolf Carnap's inductive logic. The new approach is based on truth in the consecutive finite domains of individuals. This concept will be given a constructive interpretation. What can be verifiably said about an empirical statement with respect to this concept of truth, will be explained, for which purpose a constructive notion of epistemic probability will be introduced. The aim of this study is also to improve Carnap's inductive logic. The study addresses the problem of justifying the use of an "inductivist" method in Carnap's lambda-continuum. A correction rule for adjusting the inductive method itself in the course of obtaining evidence will be introduced. Together with the constructive interpretation of probability, the correction rule yields positive prior probabilities for universal generalizations in infinite domains.

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.

Dependence Logic: Investigations into Higher-Order Semantics Defined on Teams

This thesis is a study of a rather new logic called dependence logic and its closure under classical negation, team logic. In this thesis, dependence logic is investigated from several aspects. Some rules are presented for quantifier swapping in dependence logic and team logic. Such rules are among the basic tools one must be familiar with in order to gain the required intuition for using the logic for practical purposes. The thesis compares Ehrenfeucht-Fraïssé (EF) games of first order logic and dependence logic and defines a third EF game that characterises a mixed case where first order formulas are measured in the formula rank of dependence logic. The thesis contains detailed proofs of several translations between dependence logic, team logic, second order logic and its existential fragment. Translations are useful for showing relationships between the expressive powers of logics. Also, by inspecting the form of the translated formulas, one can see how an aspect of one logic can be expressed in the other logic. The thesis makes preliminary investigations into proof theory of dependence logic. Attempts focus on finding a complete proof system for a modest yet nontrivial fragment of dependence logic. A key problem is identified and addressed in adapting a known proof system of classical propositional logic to become a proof system for the fragment, namely that the rule of contraction is needed but is unsound in its unrestricted form. A proof system is suggested for the fragment and its completeness conjectured. Finally, the thesis investigates the very foundation of dependence logic. An alternative semantics called 1-semantics is suggested for the syntax of dependence logic. There are several key differences between 1-semantics and other semantics of dependence logic. 1-semantics is derived from first order semantics by a natural type shift. Therefore 1-semantics reflects an established semantics in a coherent manner. Negation in 1-semantics is a semantic operation and satisfies the law of excluded middle. A translation is provided from unrestricted formulas of existential second order logic into 1-semantics. Also game theoretic semantics are considerd in the light of 1-semantics.

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.

Group Beliefs : Studies on the Nature and Logic of Collective Doxastic Attitudes

This thesis studies the nature and logic of collective doxastic attitudes, or what is referred to in ordinary language as "group beliefs". Beliefs and other intentional attitudes are attributed to groups and collections of people, and such attributions are used to explain and predict the actions of groups. The thesis develops an understanding of group beliefs as voluntarily adopted views or acceptances rather than as ordinary beliefs. Such an understanding can provide new answers to questions concerning collective knowledge and justification of group beliefs, and it allows developing modal logics with collective doxastic and epistemic notions. The thesis consists of six articles. The first three articles are philosophical studies concerned with the nature of group beliefs. The last three articles are logical studies that aim at developing proof-theoretical calculi for reasoning about collective doxastic attitudes.