Two-dimensional Sgraffito automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10290121" target="_blank" >RIV/00216208:11320/14:10290121 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21230/14:00225588

Výsledek na webu

<a href="http://dx.doi.org/10.1051/ita/2014023" target="_blank" >http://dx.doi.org/10.1051/ita/2014023</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1051/ita/2014023" target="_blank" >10.1051/ita/2014023</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Two-dimensional Sgraffito automata

Popis výsledku v původním jazyce

We present a new model of a two-dimensional computing device called Sgraffito automaton. In general, the model is quite simple, which allows a clear design of computations. When restricted to one-dimensional inputs, that is, strings, the Sgraffito automaton does not exceed the power of finite-state automata. On the other hand, for two-dimensional inputs, it yields a family of picture languages with good closure properties that strictly includes the class REC of recognizable picture languages. The deterministic Sgraffito automata define a class of picture languages that includes the class of deterministic recognizable picture languages DREC, the class of picture languages that are accepted by four-way alternating automata, those that are accepted by deterministic one-marker automata, and the sudoku-deterministically recognizable picture languages, but the membership problem for the accepted languages is still decidable in polynomial time. In addition, the deterministic Sgraffito automat

Název v anglickém jazyce

Two-dimensional Sgraffito automata

Popis výsledku anglicky

We present a new model of a two-dimensional computing device called Sgraffito automaton. In general, the model is quite simple, which allows a clear design of computations. When restricted to one-dimensional inputs, that is, strings, the Sgraffito automaton does not exceed the power of finite-state automata. On the other hand, for two-dimensional inputs, it yields a family of picture languages with good closure properties that strictly includes the class REC of recognizable picture languages. The deterministic Sgraffito automata define a class of picture languages that includes the class of deterministic recognizable picture languages DREC, the class of picture languages that are accepted by four-way alternating automata, those that are accepted by deterministic one-marker automata, and the sudoku-deterministically recognizable picture languages, but the membership problem for the accepted languages is still decidable in polynomial time. In addition, the deterministic Sgraffito automat

Druh

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

CEP obor

IN - Informatika

OECD FORD obor

—

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)

Rok uplatnění

2014

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

RAIRO - Theoretical Informatics and Applications

ISSN

0988-3754

e-ISSN

—

Svazek periodika

48

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

35

Strana od-do

505-539

Kód UT WoS článku

000347978800003

EID výsledku v databázi Scopus

—