Yliopiston etusivulle Suomeksi På svenska In English Helsingin yliopisto

Compiling Simple Context Restrictions with Nondeterministic Automata

Show full item record

Avaa tiedosto Vie RefWorksiin
Title: Compiling Simple Context Restrictions with Nondeterministic Automata
Author: Yli-Jyrä, Anssi Mikael
Citation: Yli-Jyrä , A M 2011 , ' Compiling Simple Context Restrictions with Nondeterministic Automata ' , in Proceedings of the 9th International Workshop on Finite State Methods and Natural Language Processing , pp. 30-38 .
Belongs to series: International Workshop on Finite State Methods and Natural Language Processing - Proceedings of the 9th International Workshop on Finite State Methods and Natural Language Processing
Abstract: This paper describes a non-conventional method for compiling (phonological or morpho-syntactic) context restriction (CR) constraints into non-deterministic automata in finite-state tools and surface parsing systems. The method reduces any CR into a simple one that constraints the occurrences of the empty string and represents right contexts with co-determististic states. In cases where a fully deterministic representation would be exponentially larger, this kind of inward de- terminism in contexts can bring benefits over various De Morgan approaches where full determinization is necessary. In the method, an accepted word gets a unique path that is a projection of a ladder-shaped structure in the context recognizer. This projection is computed in time that is polynomial to the number of context states. However, it may be difficult to take advantage of the method in a finite-state library that coerces intermediate results into canonical automata and whose intersection operation assumes deterministic automata.
Peer review status: Peer reviewed
URI: http://hdl.handle.net/10138/29898
Date: 2011

Files in this item

Files Description Size Format View/Open
W11_4405.pdf 197.5Kb PDF View/Open
ylijyra_fsmnlp11_online_slides.pdf 570.6Kb PDF View/Open
This item appears in the following Collection(s)

Show full item record

Search Helda


Advanced Search

Browse

My Account