Describing Syntax with Star-Free Regular Expressions

Describing Syntax with Star-Free Regular Expressions Anssi Yli-Jyrã Department of General Linguistics, P.O. Box 9, FIN-00014 Univ. of Helsinki, Finland anssi .yli — jyra@helsinki fi Abstract Syntactic constraints in Koskenniemi's Finite-State Intersection Grammar (FSIG) are logically less complex than their formalism (Koskenniemi et al., 1992) would suggest: It turns out that although the constraints in Voutilainen's (1994) FSIG description of English make use of several extensions to regular expressions, the description as a whole reduces to a finite combination of union, complement and concatenation. This is an essential improvement to the descriptive complexity of ENGFSIG. The result opens a door for further anal- ysis of logical properties and possible optimizations in the FSIG descriptions. The proof contains a new formula for compiling Koskenniemi's restriction operation without any marker symbols. 1 Introduction For many years, various finite-state models of language (Roche and Schabes, 1997) have been used in surface-syntactic parsing. These mod- els can process local syntactic ambiguity effi- ciently. However, because the formalism of Finite- State Intersection Grammar (Koskenniemi, 1990; Koskenniemi et al., 1992) allows full regular expressions, its parsing is sometimes inefficient (Tapanainen, 1997); many FSIG constraint au- tomata can reduce ambiguity only after they have scanned the whole sentence. Regular expressions in FSIG can be viewed as a grammar-writing tool that should be as flexible as possible. This viewpoint has led to introduction of new features into the formalism (Koskenniemi et al., 1992). It is, however, very difficult to make any a priori generalizations of the structural prop- erties of automata as long as we allow unrestricted use of regular expressions. A complementary view is to analyze the prop- erties of languages described by FSIG regular expressions. We can carry out the analysis by checking whether the languages can be described with a restricted class of regular expressions. For many such classes of expressions, there also ex- ists a group-theoretic characterization (Pin, 1986). Moreover, if the analyzed regular language has favorable properties, some problems, e.g. the string membership problem, can be solved faster by means of specialized algorithms. A language can be described with a star-free regular expression if it can be constructed from alphabet symbols by application of union (A U B), complementation (A) and finite concatena- tion (AB), that is, without the Kleene closure (A*). The theoretical importance of this class of languages is supported by its characterization in terms of finite aperiodic syntactic monoids (Schtitzenberger, 1965) and by its definability in first-order logic over strings (McNaughton and Pa- pert, 1971). The class has also a lot of practical importance, because many languages in it admit extremely simple implementations (ibid.). The question of the star-freeness restriction on FSIG constraints has not been studied before, pos- sibly because of the following observations: (i) An acyclic automaton representing readings of the sentence has a central role in FSIG parsing (Tapanainen, 1997). Star-freeness of the constraints is a minor restriction when compared to the finiteness of this language. 379 (ii) If automata states are encoded as "traces" into strings, …

Content truncated to 500 words