On the Gap-Complexity of Simple RL-Automata

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F06%3A00002821" target="_blank" >RIV/00216208:11320/06:00002821 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On the Gap-Complexity of Simple RL-Automata

Original language description

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. Here we introduce and study a new type of restarting automaton, the so-called t-sRL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size 1 only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. Herewe study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-sRL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-sRL-automata with an unbounded number of gapsaccept NP-complete languages.

Czech name

O děrové-složitosti jednoduchých RL- automatů

Czech description

Redukční analýza je metodou používanou v lingvistice pro kontrolu správnosti vět přirozených jazyků. Tato metoda je modelována pomocí restartovacích automatů. Zde se zavádí a studuje nový typ restartovacích automatů, tak zvaný t-sRL-automat, jenž je RL-automatem s pracovním oknem velikosti 1, a který splňuje podmínku minimální acceptance. Na druhé straně, může provádět až vypouštěcích kroků v cyklu. Zde studujeme tzv. gap-complexity těchto automatů. Membership problém pro jazyky přijímané pomocí t-sRL-automatů s omezeným počtem děr (gaps) je řešitelný v polynomiálním čase. Na druhé straně, t-sRL-automaty neomezeým počtem děr přijímají NP-úplné jazyky.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2006

Confidentiality

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

Name of the periodical

Lecture Notes In Computer Science

ISSN

0302-9743

e-ISSN

—

Volume of the periodical

4036/2006

Issue of the periodical within the volume

4036

Country of publishing house

CZ - CZECH REPUBLIC

Number of pages

12

Pages from-to

83-94

UT code for WoS article

—

EID of the result in the Scopus database

—