Deterministic Two-Dimensional Languages over One-Letter Alphabet

DOI10.1007/978-3-540-75414-5_9zbMath1148.68395OpenAlexW1504576635MaRDI QIDQ3522864

Marcella Anselmo, Marina Madonia

Publication date: 4 September 2008

Published in: Algebraic Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-75414-5_9

zbMATH Keywords

determinismtwo-dimensional languagesautomata and formal languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

Tiling Recognizable Two-Dimensional Languages ⋮ Recognizable vs. Regular Picture Languages ⋮ Framed Versus Unframed Two-Dimensional Languages ⋮ Deterministic and unambiguous two-dimensional languages over one-letter alphabet ⋮ Picture Languages Generated by Assembling Tiles

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
• Complexity of two-dimensional patterns
• Nondeterminism versus determinism of finite automata over directed acyclic graphs
• Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation
• New operations and regular expressions for two-dimensional languages over one-letter alphabet
• Semigroups, Presburger formulas, and languages
• Two-dimensional finite automata and unacceptable functions
• Unambiguous recognizable two-dimensional languages
• On the Complexity of Unary Tiling-Recognizable Picture Languages
• Regular expressions and context-free grammars for picture languages
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages
• Theory Is Forever
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures

This page was built for publication: Deterministic Two-Dimensional Languages over One-Letter Alphabet