Two-dimensional Sgraffito automata

DOI10.1051/ita/2014023zbMath1328.68117MaRDI QIDQ5248876

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 language; REC; bounded Turing machine; Sgraffito automaton

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Complexity of Matching Sets of Two-Dimensional Patterns by Two-Dimensional On-Line Tessellation Automaton, Automata with cyclic move operations for picture languages, Unnamed Item, 2D oxide picture languages and their properties, Deterministic ordered restarting automata for picture languages, Two-dimensional pattern matching against local and regular-like picture languages, Two-dimensional models, Some classes of rational functions for pictures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some properties of two-dimensional on-line tessellation acceptors
• Complexity of two-dimensional patterns
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Two-Dimensional Sgraffito Automata
• New Results on Deterministic Sgraffito Automata
• Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata
• Weight-Reducing Hennie Machines and Their Descriptional Complexity
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages
• One-tape, off-line Turing machine computations
• A note on one-pebble two-dimensional Turing machines