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

DOI10.1016/J.TCS.2008.12.009MaRDI QIDQ1013124zbMATH OpenOpenAlexFDO

Authors Marcella Anselmo, Maria 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 automataunambiguitytwo-dimensional languagesone-letter alphabet

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Deterministic Two-Dimensional Languages over One-Letter Alphabet
• Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages
• Unambiguous recognizable two-dimensional languages
• A Note on Unambiguity, Finite Ambiguity and Complementation in Recognizable Two-Dimensional Languages
• A brief excursion inside the class of tiling recognizable two-dimensional languages

Cites work

• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1438757 (Why is no real title available?)
• Complexity of two-dimensional patterns
• Deterministic Two-Dimensional Languages over One-Letter Alphabet
• 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
• 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
• Rational sets in commutative monoids
• Recognizable vs. Regular Picture Languages
• Regular expressions and context-free grammars for picture 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
• Weighted Picture Automata and Weighted Logics

Cited in

(12)

• Deterministic Two-Dimensional Languages over One-Letter Alphabet
• Relative approximate bisimulations for fuzzy picture automata
• Two-dimensional rational automata: a bridge unifying one- and two-dimensional language theory
• Exploring inside tiling recognizable picture languages to find deterministic subclasses
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages
• Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages
• Classes of two-dimensional languages and recognizability conditions
• Framed Versus Unframed Two-Dimensional Languages
• Comparing necessary conditions for recognizability of two-dimensional languages
• Picture codes and deciphering delay
• Two-dimensional models
• Structure and properties of strong prefix codes of pictures

This page was built for publication: Deterministic and unambiguous 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 Q1013124)