Two-Dimensional Limited Context Restarting Automata
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10336250" target="_blank" >RIV/00216208:11320/16:10336250 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.3233/FI-2016-1437" target="_blank" >http://dx.doi.org/10.3233/FI-2016-1437</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.3233/FI-2016-1437" target="_blank" >10.3233/FI-2016-1437</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Two-Dimensional Limited Context Restarting Automata
Popis výsledku v původním jazyce
Motivated by possible machine learning of picture languages, we introduce a new two-dimensional automaton called two-dimensional limited context restarting automaton. Our model is a simplification of the two-dimensional restarting tiling automaton, from which it differs in that it does not require to scan input pictures in a fixed order. We show that the two-dimensional limited context restarting automaton is equally powerful as the two-dimensional sgraffito automaton. Moreover, the correctness preserving version of the new model, while still being nondeterministic, is equivalent to the deterministic sgraffito automaton. However, the property of being correctness preserving is not even semi-decidable for two-dimensional limited context restarting automata.
Název v anglickém jazyce
Two-Dimensional Limited Context Restarting Automata
Popis výsledku anglicky
Motivated by possible machine learning of picture languages, we introduce a new two-dimensional automaton called two-dimensional limited context restarting automaton. Our model is a simplification of the two-dimensional restarting tiling automaton, from which it differs in that it does not require to scan input pictures in a fixed order. We show that the two-dimensional limited context restarting automaton is equally powerful as the two-dimensional sgraffito automaton. Moreover, the correctness preserving version of the new model, while still being nondeterministic, is equivalent to the deterministic sgraffito automaton. However, the property of being correctness preserving is not even semi-decidable for two-dimensional limited context restarting automata.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
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)
Ostatní
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ů
Údaje specifické pro druh výsledku
Název periodika
Fundamenta Informaticae
ISSN
0169-2968
e-ISSN
—
Svazek periodika
148
Číslo periodika v rámci svazku
3-4
Stát vydavatele periodika
PL - Polská republika
Počet stran výsledku
32
Strana od-do
309-340
Kód UT WoS článku
000391742900005
EID výsledku v databázi Scopus
2-s2.0-85008419343