This HTML5 document contains 43 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n15http://localhost/temp/predkladatel/
n20http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n10http://linked.opendata.cz/resource/domain/vavai/projekt/
n11http://linked.opendata.cz/ontology/domain/vavai/
shttp://schema.org/
rdfshttp://www.w3.org/2000/01/rdf-schema#
skoshttp://www.w3.org/2004/02/skos/core#
n4http://linked.opendata.cz/ontology/domain/vavai/riv/
n6http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n8http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n7http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n17http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n14http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n18http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F68407700%3A21230%2F14%3A00225588%21RIV15-GA0-21230___/
n19http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n9http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n5http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F68407700%3A21230%2F14%3A00225588%21RIV15-GA0-21230___
rdf:type
n11:Vysledek skos:Concept
rdfs:seeAlso
http://www.rairo-ita.org/articles/ita/abs/2014/05/ita130054/ita130054.html
dcterms:description
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 automata accept some unary picture languages that are outside of the class REC. 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 automata accept some unary picture languages that are outside of the class REC.
dcterms:title
Two-dimensional Sgraffito automata Two-dimensional Sgraffito automata
skos:prefLabel
Two-dimensional Sgraffito automata Two-dimensional Sgraffito automata
skos:notation
RIV/68407700:21230/14:00225588!RIV15-GA0-21230___
n4:aktivita
n14:P
n4:aktivity
P(GAP103/10/0783), P(GAP202/10/1333)
n4:cisloPeriodika
5
n4:dodaniDat
n5:2015
n4:domaciTvurceVysledku
n20:8547777
n4:druhVysledku
n9:J
n4:duvernostUdaju
n7:S
n4:entitaPredkladatele
n18:predkladatel
n4:idSjednocenehoVysledku
51540
n4:idVysledku
RIV/68407700:21230/14:00225588
n4:jazykVysledku
n17:eng
n4:klicovaSlova
Bounded turing machine; REC; Sgraffito automaton; Two-dimensional language
n4:klicoveSlovo
n8:REC n8:Sgraffito%20automaton n8:Two-dimensional%20language n8:Bounded%20turing%20machine
n4:kodStatuVydavatele
FR - Francouzská republika
n4:kontrolniKodProRIV
[4A3B7D0278AA]
n4:nazevZdroje
RAIRO - Theoretical Informatics and Applications
n4:obor
n19:JD
n4:pocetDomacichTvurcuVysledku
1
n4:pocetTvurcuVysledku
3
n4:projekt
n10:GAP103%2F10%2F0783 n10:GAP202%2F10%2F1333
n4:rokUplatneniVysledku
n5:2014
n4:svazekPeriodika
48
n4:tvurceVysledku
Mráz, F. Průša, Daniel Otto, F.
s:issn
0988-3754
s:numberOfPages
35
n6:doi
10.1051/ita/2014023
n15:organizacniJednotka
21230