Deterministic ordered 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%2F15%3A10319916" target="_blank" >RIV/00216208:11320/15:10319916 - isvavai.cz</a>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Deterministic ordered restarting automata for picture languages

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Deterministic ordered restarting automata for picture languages

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

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

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

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 periodika

Acta Informatica

ISSN

0001-5903

e-ISSN

—

Svazek periodika

52

Číslo periodika v rámci svazku

7-8

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

31

Strana od-do

593-623

Kód UT WoS článku

000362361800003

EID výsledku v databázi Scopus

2-s2.0-84947867277