Cyclically extended variants of Sgraffito and restarting automata for picture languages
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Cyclically extended variants of Sgraffito and restarting automata for picture languages
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA15-04960S" target="_blank" >GA15-04960S: SeLeCt - Structures, Learning and Cognition</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
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
—
Number of pages
15
Pages from-to
259-273
Publisher name
Österreichische Computer Gesellschaft
Place of publication
Wien
Event location
Debrecen
Event date
Aug 29, 2016
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—