Projects per year
Abstract
Syntactic constraints in Koskenniemi’s FiniteState 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.
Translated title of the contribution  Syntaksin kuvaaminen käyttäen tähdettömiä säännöllisiä lausekkeita 

Original language  English 
Title of host publication  Proceedings of the EACL 2003 
Editors  Ann Copestake, Jan Hajic 
Number of pages  8 
Volume  10 
Publication date  2003 
Pages  379386 
Publication status  Published  2003 
MoE publication type  A4 Article in conference proceedings 
Event  EACL, Conference of the European Chapter of the Association for Computational Linguistics  Budapest, Hungary Duration: 12 Apr 2003 → 17 Apr 2003 Conference number: 10 
Bibliographical note
Has been cited by:1. Nathan Vaillette. Dissertation. 2004
2. András Kornai. Mathematical Linguistics. Springer Verlag. 2008.
3. Mans Hulden, Regular Expressions and Predicate Logic in FiniteState Language
Processing, Proceeding of the 2009 conference on FiniteState Methods and Natural Language Processing: Postproceedings of the 7th International Workshop FSMNLP 2008, p.8297, July 11, 2009
Proceeding volume: 10
Fields of Science
 612 Languages and Literature
 surface syntax
 constraints
 grammar
 113 Computer and information sciences
 regular expressions
 Kleene closure
 111 Mathematics
 descriptive complexity
 firstorder logic
Projects
 1 Finished

CSPFSIGTREES: Efficient Parsing with FiniteState Constraint Satisfaction
YliJyrä, A., Koskenniemi, K. & Carlson, L.
01/01/2002 → 13/09/2005
Project: Research project