Degrees of non-monotonicity for restarting automata,

Result code in IS VaVaI

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

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Degrees of non-monotonicity for restarting automata,

Original language description

In the literature various notions of monotonicity for restarting automata have been studied. Here we introduce two new variants of monotonicity for restarting automata and for two-way restarting automata: left-monotonicity and right-left monotonicity. Itis shown that the Various types of deterministic and nondeterministic restarting automata without auxiliary symbols, these notions yield infinite hierarchies, and we compare these hierarchies to each other. Further, as a tool used to simplify some of the proofs, the shrinking restarting automaton is introduced, which is a generalization of the standard restarting automaton to the weight-reducing case. Some of the consequences of this generalization are also discussed.

Czech name

Stupně monotonie pro restartovací automaty

Czech description

V pramenech se studují rozličné varianty pojmu monotonie pro restartovací automaty. Zde se zavádí dvě nové varianty monotonie pro restartovací automaty: levá monotonie a pravo-levá monotonie. Jsou presentovány a porovnávány rozličné hierarchie jazyků založené na těchto pojmech. Zprvu jako technický prostředek byly zavedeny shrinking restartovací automaty , které zobecňují standardní restartovací automaty tak, že místo zkracování zmenšují jisté ohodnocení řetězů. Jsou diskutovány důsledky této generalizace.

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

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Volume of the periodical

366

Issue of the periodical within the volume

366

Country of publishing house

FR - FRANCE

Number of pages

34

Pages from-to

1-34

UT code for WoS article

—

EID of the result in the Scopus database

—