A computational model for tiling recognizable two-dimensional languages

DOI10.1016/j.tcs.2009.03.016zbMath1191.68371OpenAlexW2083514099MaRDI QIDQ840773

Dora Giammarresi, Marcella Anselmo, Marina Madonia

Publication date: 14 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.016

zbMATH Keywords

determinismfinite automatatwo-dimensional languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

EXPLORING INSIDE TILING RECOGNIZABLE PICTURE LANGUAGES TO FIND DETERMINISTIC SUBCLASSES ⋮ Snake-Deterministic Tiling Systems ⋮ Non-expandable non-overlapping sets of pictures ⋮ Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory ⋮ Unbordered Pictures: Properties and Construction ⋮ Full sets of pictures to encode pictures ⋮ Unnamed Item ⋮ 2D oxide picture languages and their properties ⋮ Weighted three directions OTA and weighted hexapolic picture automata ⋮ Some classes of rational functions for pictures ⋮ RESTARTING TILING AUTOMATA ⋮ Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages ⋮ Sets of Pictures Avoiding Overlaps ⋮ Deterministic ordered restarting automata for picture languages ⋮ Two-dimensional models

Cites Work

• Unnamed Item
• Two-dimensional alternative Turing machines
• Three-way automata on rectangular types over a one-letter alphabet
• Some properties of two-dimensional on-line tessellation acceptors
• A note on two-dimensional finite automata
• Complexity of two-dimensional patterns
• A SAT-based parser and completer for pictures specified by tiling
• Unambiguous recognizable two-dimensional languages
• Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages
• Weighted Picture Automata and Weighted Logics
• Implementation and Application of Automata