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

Changes in Beer Labels and their Meaning : A Holistic Approach to the Semiosic Process

The purpose of this study is to find a framework for a holistic approach to, and form a conceptual toolbox for, investigating changes in signs and in their interpretation. Charles S. Peirce s theory of signs in a communicative perspective is taken as a basis for the framework. The concern directing the study is the problem of a missing framework in analysing signs of visual artefacts from a holistic perspective as well as that of the missing conceptual tools. To discover the possibility of such a holistic approach to semiosic processes and to form a conceptual toolbox the following issues are discussed: i) how the many Objects with two aspects involved in Peirce s definition of sign-action, promote multiple semiosis arising from the same sign by the same Interpretant depending on the domination of the Objects; ii) in which way can the relation of the individual and society or group be made more apparent in the construction of the self since this construction is intertwined with the process of meaning-creation and interpretation; iii) how to account for the fundamental role of emotions in semiosis, and the relation of emotions with the often neglected topic of embodiment; iv) how to take into account the dynamic, mediating and processual nature of sign-action in analysing and understanding the changes in signs and in the interpretation of signs. An interdisciplinary approach is chosen for this dissertation. Concepts that developed within social psychology, developmental psychology, neurosciences and semiotics, are discussed. The common aspect of the approaches is that they in one way or another concentrate on mediation provided by signs in explaining human activity and cognition. The holistic approach and conceptual toolbox found are employed in a case study. This consists of an analysis of beer brands including a comparison of brands from two different cultures. It becomes clear that different theories and approaches have mutual affinities and do complement each other. In addition, the affinities in different disciplines somewhat provide credence to the various views. From the combined approach described, it becomes apparent that by the semiosic process, the emerging semiotic self intertwined with the Umwelt, including emotions, can be described. Seeing the interpretation and meaning-making through semiosis allows for the analysis of groups, taking into account the embodied and emotional component. It is concluded that emotions have a crucial role in all human activity, including so-called reflective thinking, and that emotions and embodiment should be consciously taken into account in analysing signs, the interpretation, and in changes of signs and interpretations from both the social and individual level. The analysis of the beer labels expresses well the intertwined nature of the relationship between signs, individual consumers and society. Many direct influences from society on the label design are found, and also some indirect attitude changes that become apparent from magazines, company reports, etc. In addition, the analysis brings up the issues of the unifying tendency of the visual artefacts of different cultures, but also demonstrates that the visual artefacts are able to hold the local signs and meanings, and sometimes are able to represent the local meanings although the signs have changed in the unifying process.

The influence of HIV infection to the periodontium; a clinical, microbiological, and enzymological study

The main targets of human immunodeficiency virus (HIV) are CD4 receptors of CD4+ lymphocytes and many other cells such as monocytes/macrophages, megakaryocytes, peripheral blood dendritic cells, follicular dendritic cells (DC), epidermal Langerhans cells, and astrocytes. Infection and killing of CD4+ lymphocytes or false reaction of the body to HIV infection and the spontaneous apoptosis of CD4+ lymphocytes decrease CD4+ lymphocyte counts leading to immunosuppression, further disease progression, and appearance of opportunistic infections and malignancies. Oral manifestations are considered to be among the first signs of HIV infection. Enhanced degradation of extracellular matrix and basement membrane components in oral diseases including periodontitis is caused by Zn-dependent enzymes called matrix metalloproteinases (MMPs). The levels and degrees of activation of MMP-1, -2, -3, -7, -8, -9, -25, -26, tissue inhibitors of MMPs (TIMP)-1 and -2, and myeloperoxidase (MPO) and collagenolytic/gelatinolytic activities, and also Ig A, -G, and -M, total protein, and albumin levels in a two-year follow-up were studied from salivary samples. The expression of MMP-7, -8, -9, -25, and -26 immunoreactivities in gingival tissue specimens were studied. Healthy HIV-negative subjects served as controls. All studied clinical periodontal parameters and microbiological evaluation of the periodontopathogens showed that periodontal health of the HIV-positive patients was moderately decreased in comparison to the healthy controls. The levels of Candida in the periodontal pockets and salivary MPO increased with the severity of HIV infection. Immunoreactivities and levels of MMPs and TIMPs, and MMP activities (collagenase, gelatinase) were enhanced in the HIV-positive patient salivary samples relative to the healthy controls regardless of the phase of HIV infection. However, these parameters did not reflect periodontal status in a similar way as in the generally healthy periodontitis patients. Salivary total protein, albumin, IgA, -G, and -M levels were significantly higher in all phases of HIV infection compared to the controls, and salivary total protein, IgG and IgM levels remained higher after two years follow-up, partly correlating with the disease progression and which may reflect the leakage of serum components into the mouth and thus a decreased mucosal barrier. Salivary analyses of MMPs and TIMPs with immunohistochemical analyses showed that HIV infection could predispose to periodontal destruction when compared with healthy controls or the body s defence reactions associated with HIV infection may have been reflected or mediated by MMPs.