Deterministic and unambiguous two-dimensional languages over one-letter alphabet

DOI10.1016/j.tcs.2008.12.009zbMath1162.68020OpenAlexW1979836160MaRDI QIDQ1013124

Marcella Anselmo, Marina Madonia

Publication date: 16 April 2009

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

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

zbMATH Keywords

determinismfinite automatatwo-dimensional languagesunambiguityone-letter alphabet

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (8)

EXPLORING INSIDE TILING RECOGNIZABLE PICTURE LANGUAGES TO FIND DETERMINISTIC SUBCLASSES ⋮ Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory ⋮ Structure and properties of strong prefix codes of pictures ⋮ Classes of two-dimensional languages and recognizability conditions ⋮ Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages ⋮ Picture codes and deciphering delay ⋮ Framed Versus Unframed Two-Dimensional Languages ⋮ Two-dimensional models

Cites Work

• Unnamed Item
• 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
• Rational sets in commutative monoids
• Two-dimensional finite automata and unacceptable functions
• Unambiguous recognizable two-dimensional languages
• Recognizable vs. Regular Picture Languages
• Deterministic Two-Dimensional Languages over One-Letter Alphabet
• 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
• Weighted Picture Automata and Weighted Logics
• Theory Is Forever
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures

This page was built for publication: Deterministic and unambiguous two-dimensional languages over one-letter alphabet