Generalized Linear List Automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F05%3A00012176" target="_blank" >RIV/61989100:27240/05:00012176 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Generalized Linear List Automata

Popis výsledku v původním jazyce

We follow some previous studies of list automata and restarting automata and introduce a generalized and refined model -- a two-way generalized linear list automaton (GLLA) and its subclasses defined by sets of allowed operations. Motivation for the model comes from (computational) linguistics, mainly from the need to express syntactic constraints. We also present several subclasses of GLL-automata, providing some variants and extensions of the Chomsky hierarchy. Our technical results include comparingthe expressive power of automata having only move-to-the-right and delete-to-the-left operations with the class of (D)CFL ((deterministic) context-free languages); in particular we show an infinite hierarchy inside DCFL, defined by the increasing size ofthe read/write lookahead window.

Název v anglickém jazyce

Generalized Linear List Automata

Popis výsledku anglicky

We follow some previous studies of list automata and restarting automata and introduce a generalized and refined model -- a two-way generalized linear list automaton (GLLA) and its subclasses defined by sets of allowed operations. Motivation for the model comes from (computational) linguistics, mainly from the need to express syntactic constraints. We also present several subclasses of GLL-automata, providing some variants and extensions of the Chomsky hierarchy. Our technical results include comparingthe expressive power of automata having only move-to-the-right and delete-to-the-left operations with the class of (D)CFL ((deterministic) context-free languages); in particular we show an infinite hierarchy inside DCFL, defined by the increasing size ofthe read/write lookahead window.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F02%2F1456" target="_blank" >GA201/02/1456: Specializované výpočetní modely v současné informatice</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2005

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

ITAT 2004

ISBN

80-7097-589-X

ISSN

—

e-ISSN

—

Počet stran výsledku

9

Strana od-do

97-105

Název nakladatele

Univerzita P. J. Šafárika v Košiciach

Místo vydání

Košice

Místo konání akce

Popradské Pleso

Datum konání akce

16. 9. 2004

Typ akce podle státní příslušnosti

CST - Celostátní akce

Kód UT WoS článku

—