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

Linguistic grammars with very low complexity

We have presented an overview of the FSIG approach and related FSIG gram- mars to issues of very low complexity and parsing strategy. We ended up with serious optimism according to which most FSIG grammars could be decom- posed in a reasonable way and then processed efficiently.

An Efficient Constraint Grammar Parser based on Inward Deterministic Automata

Pappret conceptualizes parsning med Constraint Grammar på ett nytt sätt som en process med två viktiga representationer. En representation innehåller lokala tvetydighet och den andra sammanfattar egenskaperna hos den lokala tvetydighet klasser. Båda representationer manipuleras med ren finite-state metoder, men deras samtrafik är en ad hoc -tillämpning av rationella potensserier. Den nya tolkningen av parsning systemet har flera praktiska fördelar, bland annat det inåt deterministiska sättet att beräkna, representera och räkna om alla potentiella tillämpningar av reglerna i meningen.

Describing syntax with star-free regular expressions

Koskenniemen Äärellistilaisen leikkauskieliopin (FSIG) lauseopilliset rajoitteet ovat loogisesti vähemmän kompleksisia kuin mihin niissä käytetty formalismi vittaisi. Osoittautuukin että vaikka Voutilaisen (1994) englannin kielelle laatima FSIG-kuvaus käyttää useita säännöllisten lausekkeiden laajennuksia, kieliopin kuvaus kokonaisuutenaan palautuu äärelliseen yhdistelmään unionia, komplementtia ja peräkkäinasettelua. Tämä on oleellinen parannus ENGFSIG:n descriptiiviseen kompleksisuuteen. Tulos avaa ovia FSIG-kuvauksen loogisten ominaisuuksien syvemmälle analyysille ja FSIG kuvausten mahdolliselle optimoinnillle. Todistus sisältää uuden kaavan, joka kääntää Koskenniemien rajoiteoperaation ilman markkerimerkkejä.

Problems of Proto-Slavic Historical Nominal Morphology : On the Basis of Old Church Slavic

In this study I offer a diachronic solution for a number of difficult inflectional endings in Old Church Slavic nominal declensions. In this context I address the perhaps most disputed and the most important question of the Slavic nominal inflectional morphology: whether there was in Proto-Slavic an Auslautgesetz (ALG), a law of final syllables, that narrowed the Proto-Indo-European vowel */o/ to */u/ in closed word-final syllables. In addition, the work contains an exhaustive morphological classification of the nouns and adjectives that occur in canonical Old Church Slavic. I argue that Proto-Indo-European */o/ became Proto-Slavic */u/ before word-final */s/ and */N/. This conclusion is based on the impossibility of finding credible analogical (as opposed to phonological) explanations for the forms supporting the ALG hypothesis, and on the survival of the neuter gender in Slavic. It is not likely that the */o/-stem nominative singular ending */-u/ was borrowed from the accusative singular, because the latter would have been the only paradigmatic form with the stem vowel */-u-/. It is equally unlikely that the ending */-u/ was borrowed from the */u/-stems, because the latter constituted a moribund class. The usually stated motivation for such an analogical borrowing, i.e. a need to prevent the merger of */o/-stem masculines with neuters of the same class, is not tenable. Extra-Slavic, as well as intra-Slavic evidence suggests that phonologically-triggered mergers between two semantically opaque genders do not tend to be prevented, but rather that such mergers lead to the loss of the gender opposition in question. On the other hand, if */-os/ had not become */-us/, most nouns and, most importantly, all adjectives and pronouns would have lost the formal distinction between masculines and neuters. This would have necessarily resulted in the loss of the neuter gender. A new explanation is given for the most apparent piece of evidence against the ALG hypothesis, the nominative-accusative singular of the */es/-stem neuters, e.g. nebo 'sky'. I argue that it arose in late Proto-Slavic dialects, replacing regular nebe, under the influence of the */o/- and */yo/-stems where a correlation had emerged between a hard root-final consonant and the termination -o, on the one hand, and a soft root-final consonant and the termination -e, on the other.

Vyra enie obob čёnno-ličnogo značenija v russkom jazyke

Expressing generalized-personal meaning in Russian Based on data from Russian, this doctoral dissertation examines generalized-personal meaning that is, generic expressions referring to all human beings, people in general, each or any person (e.g. S vozrastom načinae cenit prostye ve či With age you start to appreciate simple things ). The study shares its basic theoretical orientation with functional approaches going from meaning to form . The objective of the thesis is to determine and describe the various linguistic means which can be used by the speaker to express generalized-personal meaning. The main material of the study consists of 2,000 examples collected from modern Russian literature, newspapers, and magazines. The linguistic means of expressing generalized-personal meaning are divided into three main classes. Morphological and lexico-grammatical means (22% of the material) include the use of personal pronouns and personal verbal endings. In Russian, all personal forms except the 3rd person singular can be used in a generalized-personal meaning. Lexical means (14% of the material) involve, above all, pronouns like vse all , ka dyj everyone , nikto no one , as well as the nouns čelovek man and ljudi people . In emotional speech, generalized-personal meaning can also be conveyed lexically by using utterances like da e idiot znaet even an idiot knows . In rhetorical questions the pronoun kto who can appear in this meaning (cf. Kto ne ljubit moro enoe?! Who doesn t like ice cream?! ). The third main class, syntactic means (64% of the material), consists of constructions in which the generic person is not expressed at the surface level. This class mainly includes two-component structures in which the infinitive relates to a modal predicative adverb (e.g. mo no can, be allowed to , nado must ), modal verb (e.g. stoit be worth(while) , sleduet must, be obliged to ), or predicative adverb ending in -о (e.g. trudno it is hard to , neprilično is not appropriate ). Other syntactic means are: one-component infinitive structures, so-called embedded structures, structures with a processual noun, passive constructions, and gerund constructions. The different forms of expression available in Russian are not interchangeable in all contexts. Even if a given context tolerates the substitution of one construction for another, the two expressions are never entirely synonymous. In addition to determining the range of forms which can express generalized-personal meaning, the study aims to compare these forms and to specify the conditions and possible restrictions (contextual, semantic, syntactic, stylistic, etc.) associated with the use of each construction. In Russian linguistics, the generalized-personal meaning has not been extensively studied from a functional perspective. The advantage of a meaning-based functional approach is that it gives a comprehensive picture of the diversity and distribution of the phenomenon.

Jumping numbers of a simple complete ideal in a two-dimensional regular local ring

The multiplier ideals of an ideal in a regular local ring form a family of ideals parametrized by non-negative rational numbers. As the rational number increases the corresponding multiplier ideal remains unchanged until at some point it gets strictly smaller. A rational number where this kind of diminishing occurs is called a jumping number of the ideal. In this manuscript we shall give an explicit formula for the jumping numbers of a simple complete ideal in a two dimensional regular local ring. In particular, we obtain a formula for the jumping numbers of an analytically irreducible plane curve. We then show that the jumping numbers determine the equisingularity class of the curve.

Toward a widely usable finite-state morphology workbench for less studied languages, 1: Desiderata

Most of the world’s languages lack electronic word form dictionaries. The linguists who gather such dictionaries could be helped with an efficient morphology workbench that adapts to different environments and uses. A widely usable workbench could be characterized, ideally, as generally applicable, extensible, and freely available (GEA). It seems that such a solution could be implemented in the framework of finite-state methods. The current work defines the GEA desiderata and starts a series of articles concerning these desiderata in finite- state morphology. Subsequent parts will review the state of the art and present an action plan toward creating a widely usable finite-state morphology workbench.

Public opinion on useful languages in Europe

This article analyses the results of five Eurobarometer surveys (of 1995, 1997, 1998, 2000 and 2005) designed to measure which languages Europeans consider most useful to know. Most Europeans are of the opinion that English is the most useful, followed by French and German. During the last decade the popularity of French and German as useful languages has been decreasing significantly, while English has remained universally favoured as the most useful language. French and German have lost their popularity especially among those who do not speak them as a foreign language. On the other hand, Spanish, Russian and other languages (often these include languages of neighbouring countries, minority languages or a second official language of the country in question) have kept and even increased their former level of popularity. Opinions about useful languages vary according to a respondent’s knowledge of languages, education and profession. This article analyses these differences and discusses their impact on the study of foreign languages and the future of the practice of foreign languages in Europe.