Describing syntax with star-free regular expressions

Show full item record



Permalink

http://hdl.handle.net/10138/24829

Citation

Yli-Jyrä , A M 2003 , Describing syntax with star-free regular expressions . in A Copestake & J Hajic (eds) , Proceedings of the EACL 2003 . vol. 10 , pp. 379-386 , EACL, Conference of the European Chapter of the Association for Computational Linguistics , Budapest , Hungary , 12/04/2003 . < http://www.aclweb.org/anthology/E/E03/E03-1031.pdf >

Title: Describing syntax with star-free regular expressions
Alternative title: Syntaksin kuvaaminen käyttäen tähdettömiä säännöllisiä lausekkeita
Author: Yli-Jyrä, Anssi Mikael
Other contributor: Copestake, Ann
Hajic, Jan
Contributor organization: Department of Modern Languages 2010-2017
Date: 2003
Language: eng
Number of pages: 8
Belongs to series: Proceedings of the EACL 2003
URI: http://hdl.handle.net/10138/24829
Abstract: 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ä.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.
Description: 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
Subject: 612 Languages and Literature
pintasyntaksi
kielioppi
rajoitukset
surface syntax
constraints
grammar
yt-orienterad syntax
begränsningar
grammatik
113 Computer and information sciences
säännölliset lausekkeet
Kleenen sulkeuma
regular expressions
Kleene closure
reguljära uttryck
Kleene stängning
111 Mathematics
deskriptiivinen kompleksisuus
ensimmäisen kertaluokan logiikka
descriptive complexity
first-order logic
beskrivande komplexitet
första ordingens logik
Peer reviewed: Yes
Usage restriction: openAccess
Self-archived version: acceptedVersion


Files in this item

Total number of downloads: Loading...

Files Size Format View
YliJyra_2003_dessynwitsta_sli.pdf 296.2Kb PDF View/Open
1.pdf 106.3Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record