Two-dimensional Sgraffito automata

DOI10.1051/ITA/2014023MaRDI QIDQ5248876zbMATH OpenOpenAlexFDO

Authors Daniel Průša, František Mráz, Friedrich Otto

Publication date 28 April 2015

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1051/ita/2014023

zbMATH Keywords

two-dimensional languageRECbounded Turing machineSgraffito automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Two-dimensional sgraffito automata
• New results on deterministic sgraffito automata
• Comparing two-dimensional one-marker automata to sgraffito automata
• Extended two-way ordered restarting automata for picture languages
• Two-Dimensional Limited Context Restarting Automata

Cites work

• scientific article; zbMATH DE number 1689049 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3738961 (Why is no real title available?)
• A note on one-pebble two-dimensional Turing machines
• Comparing two-dimensional one-marker automata to sgraffito automata
• Complexity of two-dimensional patterns
• Deterministic forgetting planar automata are more powerful than nondeterministic finite-state planar automata
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages
• Matrix-based complexity functions and recognizable picture languages
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• New results on deterministic sgraffito automata
• One-tape, off-line Turing machine computations
• Some properties of two-dimensional on-line tessellation acceptors
• Two-dimensional sgraffito automata
• Weight-reducing Hennie machines and their descriptional complexity

Cited in

(14)

• Automata with cyclic move operations for picture languages
• scientific article; zbMATH DE number 7584603 (Why is no real title available?)
• Two-dimensional pattern matching against local and regular-like picture languages
• A survey of two-dimensional automata theory
• Deterministic ordered restarting automata for picture languages
• Some classes of rational functions for pictures
• Complexity of matching sets of two-dimensional patterns by two-dimensional on-line tessellation automaton
• Two-dimensional sgraffito automata
• New results on deterministic sgraffito automata
• Comparing two-dimensional one-marker automata to sgraffito automata
• Two-dimensional models
• Two-dimensional automata with rotated inputs (projection-type)
• 2D oxide picture languages and their properties
• Deterministic fuzzy two-dimensional on-line tessellation automata and their languages

This page was built for publication: Two-dimensional Sgraffito automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5248876)