Deterministic Two-Dimensional Languages over One-Letter Alphabet

DOI10.1007/978-3-540-75414-5_9MaRDI QIDQ3522864zbMATH OpenOpenAlexFDO

Authors Marcella Anselmo, Maria 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

automata and formal languagesdeterminismtwo-dimensional languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Deterministic and unambiguous two-dimensional languages over one-letter alphabet
• Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages
• Tiling Recognizable Two-Dimensional Languages
• A brief excursion inside the class of tiling recognizable two-dimensional languages
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages

Cites work

• Complexity of two-dimensional patterns
• Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• New operations and regular expressions for two-dimensional languages over one-letter alphabet
• Nondeterminism versus determinism of finite automata over directed acyclic graphs
• On the Complexity of Unary Tiling-Recognizable Picture Languages
• Regular expressions and context-free grammars for picture languages
• Semigroups, Presburger formulas, and languages
• Some properties of two-dimensional on-line tessellation acceptors
• Theory Is Forever
• Three-way automata on rectangular types over a one-letter alphabet
• Two-dimensional alternative Turing machines
• Two-dimensional finite automata and unacceptable functions
• Unambiguous recognizable two-dimensional languages

Cited in

(9)

• Deterministic and unambiguous two-dimensional languages over one-letter alphabet
• New operations and regular expressions for two-dimensional languages over one-letter alphabet
• Tiling Recognizable Two-Dimensional Languages
• Recognizable vs. Regular Picture Languages
• Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages
• Framed Versus Unframed Two-Dimensional Languages
• The Complexity of Unary Tiling Recognizable Picture Languages: Nondeterministic and Unambiguous Cases
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages
• Picture Languages Generated by Assembling Tiles

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

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