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

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

Namespace Prefixes

PrefixIRI
n6http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n21http://localhost/temp/predkladatel/
n17http://purl.org/net/nknouf/ns/bibtex#
n23http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n11http://linked.opendata.cz/resource/domain/vavai/projekt/
n20http://linked.opendata.cz/resource/domain/vavai/subjekt/
n12http://linked.opendata.cz/ontology/domain/vavai/
n18https://schema.org/
shttp://schema.org/
n4http://linked.opendata.cz/ontology/domain/vavai/riv/
rdfshttp://www.w3.org/2000/01/rdf-schema#
skoshttp://www.w3.org/2004/02/skos/core#
n24http://bibframe.org/vocab/
n14http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216208%3A11320%2F13%3A10145554%21RIV14-GA0-11320___/
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/
n5http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n22http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n16http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n19http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n13http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n15http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216208%3A11320%2F13%3A10145554%21RIV14-GA0-11320___
rdf:type
n12:Vysledek skos:Concept
rdfs:seeAlso
http://link.springer.com.ezproxy.is.cuni.cz/chapter/10.1007/978-3-642-39274-0_24
dcterms:description
We compare two types of automata for accepting picture languages to each other: the two-dimensional one-marker automaton and the sgraffito automaton. On the one hand, it is shown that deterministic sgraffito automata are strictly more powerful than deterministic two-dimensional one-marker automata. On the other hand, nondeterministic two-dimensional one-marker automata accept some picture languages that cannot be accepted by sgraffito automata. However, if nondeterministic two-dimensional one-marker automata were to accept all picture languages that are accepted by (deterministic) sgraffito automata, then the complexity classes NL (nondeterministic logarithmic space) and P (deterministic polynomial time) would coincide. Accordingly, it is likely that the classes of picture languages accepted by these two types of nondeterministic automata are incomparable under inclusion. We compare two types of automata for accepting picture languages to each other: the two-dimensional one-marker automaton and the sgraffito automaton. On the one hand, it is shown that deterministic sgraffito automata are strictly more powerful than deterministic two-dimensional one-marker automata. On the other hand, nondeterministic two-dimensional one-marker automata accept some picture languages that cannot be accepted by sgraffito automata. However, if nondeterministic two-dimensional one-marker automata were to accept all picture languages that are accepted by (deterministic) sgraffito automata, then the complexity classes NL (nondeterministic logarithmic space) and P (deterministic polynomial time) would coincide. Accordingly, it is likely that the classes of picture languages accepted by these two types of nondeterministic automata are incomparable under inclusion.
dcterms:title
Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata
skos:prefLabel
Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata
skos:notation
RIV/00216208:11320/13:10145554!RIV14-GA0-11320___
n12:predkladatel
n20:orjk%3A11320
n4:aktivita
n22:P
n4:aktivity
P(GAP103/10/0783), P(GAP202/10/1333)
n4:dodaniDat
n15:2014
n4:domaciTvurceVysledku
n23:5680050
n4:druhVysledku
n13:D
n4:duvernostUdaju
n5:S
n4:entitaPredkladatele
n14:predkladatel
n4:idSjednocenehoVysledku
66118
n4:idVysledku
RIV/00216208:11320/13:10145554
n4:jazykVysledku
n16:eng
n4:klicovaSlova
two-dimensional one-marker automaton; sgraffito automaton; recognizable picture languages; picture languages
n4:klicoveSlovo
n8:two-dimensional%20one-marker%20automaton n8:recognizable%20picture%20languages n8:sgraffito%20automaton n8:picture%20languages
n4:kontrolniKodProRIV
[6AF49D3F1118]
n4:mistoKonaniAkce
Halifax, Kanada
n4:mistoVydani
Berlin
n4:nazevZdroje
Implementation and Application of Automata
n4:obor
n19:IN
n4:pocetDomacichTvurcuVysledku
1
n4:pocetTvurcuVysledku
3
n4:projekt
n11:GAP103%2F10%2F0783 n11:GAP202%2F10%2F1333
n4:rokUplatneniVysledku
n15:2013
n4:tvurceVysledku
Mráz, František Otto, Friedrich Průša, Daniel
n4:typAkce
n6:WRD
n4:zahajeniAkce
2013-07-16+02:00
s:issn
0302-9743
s:numberOfPages
12
n24:doi
10.1007/978-3-642-39274-0_24
n17:hasPublisher
Springer-Verlag
n18:isbn
978-3-642-39273-3
n21:organizacniJednotka
11320