Cyclically extended variants of Sgraffito and restarting automata for picture languages

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10336417" target="_blank" >RIV/00216208:11320/16:10336417 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Cyclically extended variants of Sgraffito and restarting automata for picture languages

Popis výsledku v původním jazyce

Here we introduce and study cyclic extensions of deterministic Sgraffito automata and of deterministic two-dimensional two-way ordered restarting automata for picture languages. Such a cyclically extended automaton can move in a single step from the last column (or row) of a picture to the first column (or row). For deterministic Sgraffito automata, we show that this cyclic extension does not increase the expressive power of the model, while for deterministic two-dimensional two-way restarting automata, the expressive power is strictly increased by allowing cyclic moves. In fact, for the latter automata, we take the number of allowed cyclic moves in any column or row as a parameter, and we show that already with a single cyclic move per column (or row) the deterministic two-dimensional extended two-way restarting automaton can be simulated. On the other hand, we show that two cyclic moves per column or row already give the same expressive power as any finite number of cyclic moves. Finally, we show that for one-row pictures (that is, strings), already one cyclic move suffices.

Název v anglickém jazyce

Cyclically extended variants of Sgraffito and restarting automata for picture languages

Popis výsledku anglicky

Here we introduce and study cyclic extensions of deterministic Sgraffito automata and of deterministic two-dimensional two-way ordered restarting automata for picture languages. Such a cyclically extended automaton can move in a single step from the last column (or row) of a picture to the first column (or row). For deterministic Sgraffito automata, we show that this cyclic extension does not increase the expressive power of the model, while for deterministic two-dimensional two-way restarting automata, the expressive power is strictly increased by allowing cyclic moves. In fact, for the latter automata, we take the number of allowed cyclic moves in any column or row as a parameter, and we show that already with a single cyclic move per column (or row) the deterministic two-dimensional extended two-way restarting automaton can be simulated. On the other hand, we show that two cyclic moves per column or row already give the same expressive power as any finite number of cyclic moves. Finally, we show that for one-row pictures (that is, strings), already one cyclic move suffices.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA15-04960S" target="_blank" >GA15-04960S: SeLeCt - struktury, učení a kognice</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

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

Eighth Workshop on Non-Classical Models of Automata and Applications, NCMA 2016, Debrecen, Hungary, August 29-30, 2016. Proceedings

ISBN

978-3-903035-10-2

ISSN

—

e-ISSN

—

Počet stran výsledku

15

Strana od-do

259-273

Název nakladatele

Österreichische Computer Gesellschaft

Místo vydání

Wien

Místo konání akce

Debrecen

Datum konání akce

29. 8. 2016

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

EUR - Evropská akce

Kód UT WoS článku

—