Stupně monotonie pro restartovací automaty

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Degrees of non-monotonicity for restarting automata,

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Degrees of non-monotonicity for restarting automata,

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

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í

2006

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 periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

366

Číslo periodika v rámci svazku

366

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

34

Strana od-do

1-34

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—