Monotone deterministic RL-automata don't need auxiliary symbols

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

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Monotone deterministic RL-automata don't need auxiliary symbols

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

<a href="/en/project/GA201%2F04%2F2102" target="_blank" >GA201/04/2102: Intelligent Information Retrieval</a><br>

Continuities

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

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

Developments in Language Theory, Proceedings

ISBN

3-540-26546-5

ISSN

—

e-ISSN

—

Number of pages

12

Pages from-to

—

Publisher name

Springer

Place of publication

Berlin

Event location

Berlin

Event date

Jan 1, 2005

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000230874600025