Monotone deterministic RL-automata don't need auxiliary symbols

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F05%3A00206181" target="_blank" >RIV/00216208:11320/05:00206181 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Monotone deterministic RL-automata don't need auxiliary symbols

Popis výsledku v původním jazyce

It is known that for monotone deterministic one-way restarting automata, the use of auxiliary symbols does not increase the expressive power. Here we show that the same is true for deterministic two-way restarting automata that are right- or left-monotone. Actually in these cases it suffices to admit delete operations instead of the more general rewrite operations. In addition, we characterize the classes of languages that axe accepted by these types of two-way restarting automata by certain combinations of deterministic pushdown automata and deterministic transducers.

Název v anglickém jazyce

Monotone deterministic RL-automata don't need auxiliary symbols

Popis výsledku anglicky

It is known that for monotone deterministic one-way restarting automata, the use of auxiliary symbols does not increase the expressive power. Here we show that the same is true for deterministic two-way restarting automata that are right- or left-monotone. Actually in these cases it suffices to admit delete operations instead of the more general rewrite operations. In addition, we characterize the classes of languages that axe accepted by these types of two-way restarting automata by certain combinations of deterministic pushdown automata and deterministic transducers.

Druh

D - Stať ve sborníku

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F04%2F2102" target="_blank" >GA201/04/2102: Inteligentní vyhledávání</a><br>

Návaznosti

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

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

Developments in Language Theory, Proceedings

ISBN

3-540-26546-5

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Berlin

Datum konání akce

1. 1. 2005

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

WRD - Celosvětová akce

Kód UT WoS článku

000230874600025