Deterministic ordered restarting automata for picture languages

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10319916" target="_blank" >RIV/00216208:11320/15:10319916 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s00236-015-0230-5" target="_blank" >http://dx.doi.org/10.1007/s00236-015-0230-5</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00236-015-0230-5" target="_blank" >10.1007/s00236-015-0230-5</a>

Result language
angličtina
Original language name
Deterministic ordered restarting automata for picture languages
Original language description
The ordered restarting automaton (processing strings) is introduced, and it is shown that its nondeterministic variant is very expressive, as it accepts some languages that are not even context-free, while the deterministic ordered restarting automata just accept the regular languages. Then three different extensions of the deterministic ordered restarting automaton to two-dimensional inputs are defined that differ in the way in which they can move their read/write windows. We compare the classes of picture languages that these types of automata accept to each other and to some well studied classes of picture languages from the literature, and we present some closure and non-closure properties for them.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
<a href="/en/project/GA15-04960S" target="_blank" >GA15-04960S: SeLeCt - Structures, Learning and Cognition</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)