Generalized Linear List Automata

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Generalized Linear List Automata

Original language description

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.

Czech name

Generalized Linear List Automata

Czech description

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.

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/GA201%2F02%2F1456" target="_blank" >GA201/02/1456: Specialized computational models in contemporary computer science</a><br>

Continuities

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

Publication year

2005

Confidentiality

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

Article name in the collection

ITAT 2004

ISBN

80-7097-589-X

ISSN

—

e-ISSN

—

Number of pages

9

Pages from-to

97-105

Publisher name

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

Place of publication

Košice

Event location

Popradské Pleso

Event date

Sep 16, 2004

Type of event by nationality

CST - Celostátní akce

UT code for WoS article

—