tailieunhanh - Báo cáo khoa học: "Describing Syntax with Star-Free Regular Expressions"

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. | Describing Syntax with Star-Free Regular Expressions Anssi Yli-Jyra Department of General Linguistics . Box 9 FIN-00014 Univ of Helsinki Finland 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 analysis 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 models can process local syntactic ambiguity efficiently. 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 automata 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 properties of automata as long as we allow unrestricted use of regular expressions. A complementary view is to analyze the properties 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 .