AUTOMATA WITH CYCLIC MOVE OPERATIONS 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%2F18%3A10408529" target="_blank" >RIV/00216208:11320/18:10408529 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=QfzYUVNyNz" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=QfzYUVNyNz</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1051/ita/2018018" target="_blank" >10.1051/ita/2018018</a>
Alternative languages
Result language
angličtina
Original language name
AUTOMATA WITH CYCLIC MOVE OPERATIONS FOR PICTURE LANGUAGES
Original language description
Here, we study the cyclic extensions of 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 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
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
2018
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
Name of the periodical
RAIRO - Theoretical Informatics and Applications
ISSN
0988-3754
e-ISSN
—
Volume of the periodical
52
Issue of the periodical within the volume
2-4
Country of publishing house
FR - FRANCE
Number of pages
17
Pages from-to
235-251
UT code for WoS article
000459294200010
EID of the result in the Scopus database
2-s2.0-85062222911