About: Two-dimensional Sgraffito automata

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Two-dimensional Sgraffito automata Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://www.rairo-ita.org/articles/ita/abs/2014/05/ita130054/ita130054.html
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. (en)
Title	Two-dimensional Sgraffito automata Two-dimensional Sgraffito automata (en)
skos:prefLabel	Two-dimensional Sgraffito automata Two-dimensional Sgraffito automata (en)
skos:notation	RIV/68407700:21230/14:00225588!RIV15-GA0-21230___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(GAP103/10/0783), P(GAP202/10/1333)
http://linked.open...iv/cisloPeriodika	5
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Průša, Daniel
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	České vysoké učení technické v Praze / Fakulta elektrotechnická
http://linked.open...dnocenehoVysledku	51540
http://linked.open...ai/riv/idVysledku	RIV/68407700:21230/14:00225588
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Bounded turing machine; REC; Sgraffito automaton; Two-dimensional language (en)
http://linked.open.../riv/klicoveSlovo	REC Bounded turing machine Sgraffito automaton Two-dimensional language
http://linked.open...odStatuVydavatele	FR - Francouzská republika
http://linked.open...ontrolniKodProRIV	[4A3B7D0278AA]
http://linked.open...i/riv/nazevZdroje	RAIRO - Theoretical Informatics and Applications
http://linked.open...in/vavai/riv/obor	JD
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	NoSCoM: Non-Standard Computational Models and Their Applications in Complexity, Linguistics, and Learning Structure and its impact for recognition
http://linked.open...UplatneniVysledku	2014
http://linked.open...v/svazekPeriodika	48
http://linked.open...iv/tvurceVysledku	Průša, Daniel Mráz, F. Otto, F.
issn	0988-3754
number of pages	35 (xsd:int)
http://bibframe.org/vocab/doi	10.1051/ita/2014023
http://localhost/t...ganizacniJednotka	21230

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software