Describing syntax with star-free regular expressions

Anssi Mikael Yli-Jyrä

Describing syntax with star-free regular expressions

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

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.

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	379-386
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 Finite-State Language
Processing, Proceeding of the 2009 conference on Finite-State Methods and Natural Language Processing: Post-proceedings of the 7th International Workshop FSMNLP 2008, p.82-97, 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
first-order logic

Access to Document

the article PDFAccepted author manuscript, 106 KB
The original slides presented to the main conferenceAccepted author manuscript, 296 KB

http://www.aclweb.org/anthology/E/E03/E03-1031.pdf

CSP-FSIG-TREES: Efficient Parsing with Finite-State Constraint Satisfaction
Yli-Jyrä, A., Koskenniemi, K. & Carlson, L.
01/01/2002 → 13/09/2005
Project: Research project

Cite this

@inproceedings{facfad19fb9b429fb8ba3d5f9416fad9,

title = "Describing syntax with star-free regular expressions",

abstract = "Syntactic constraints in Koskenniemi{\textquoteright}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{\textquoteright}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{\textquoteright}s restriction operation without any marker symbols.",

keywords = "612 Languages and Literature, pintasyntaksi, kielioppi, rajoitukset, surface syntax, constraints, grammar, yt-orienterad syntax, begr{\"a}nsningar, grammatik, 113 Computer and information sciences, s{\"a}{\"a}nn{\"o}lliset lausekkeet, Kleenen sulkeuma, regular expressions, Kleene closure, regulj{\"a}ra uttryck, Kleene st{\"a}ngning, 111 Mathematics, deskriptiivinen kompleksisuus, ensimm{\"a}isen kertaluokan logiikka, descriptive complexity, first-order logic, beskrivande komplexitet, f{\"o}rsta ordingens logik",

author = "Yli-Jyr{\"a}, {Anssi Mikael}",

note = "Has been cited by: 1. Nathan Vaillette. Dissertation. 2004 2. Andr{\'a}s Kornai. Mathematical Linguistics. Springer Verlag. 2008. 3. Mans Hulden, Regular Expressions and Predicate Logic in Finite-State Language Processing, Proceeding of the 2009 conference on Finite-State Methods and Natural Language Processing: Post-proceedings of the 7th International Workshop FSMNLP 2008, p.82-97, July 11, 2009 Proceeding volume: 10; EACL, Conference of the European Chapter of the Association for Computational Linguistics ; Conference date: 12-04-2003 Through 17-04-2003",

year = "2003",

language = "English",

volume = "10",

pages = "379--386",

editor = "Ann Copestake and Jan Hajic",

booktitle = "Proceedings of the EACL 2003",

}

TY - GEN

T1 - Describing syntax with star-free regular expressions

AU - Yli-Jyrä, Anssi Mikael

N1 - Conference code: 10

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - 612 Languages and Literature

KW - pintasyntaksi

KW - kielioppi

KW - rajoitukset

KW - surface syntax

KW - constraints

KW - grammar

KW - yt-orienterad syntax

KW - begränsningar

KW - grammatik

KW - 113 Computer and information sciences

KW - säännölliset lausekkeet

KW - Kleenen sulkeuma

KW - regular expressions

KW - Kleene closure

KW - reguljära uttryck

KW - Kleene stängning

KW - 111 Mathematics

KW - deskriptiivinen kompleksisuus

KW - ensimmäisen kertaluokan logiikka

KW - descriptive complexity

KW - first-order logic

KW - beskrivande komplexitet

KW - första ordingens logik

M3 - Conference contribution

VL - 10

SP - 379

EP - 386

BT - Proceedings of the EACL 2003

A2 - Copestake, Ann

A2 - Hajic, Jan

T2 - EACL, Conference of the European Chapter of the Association for Computational Linguistics

Y2 - 12 April 2003 through 17 April 2003

ER -

Describing syntax with star-free regular expressions

Abstract

Bibliographical note

Fields of Science

Access to Document

Projects

CSP-FSIG-TREES: Efficient Parsing with Finite-State Constraint Satisfaction

Cite this