Classes of two-dimensional languages and recognizability conditions

DOI10.1051/ita/2011003zbMath1211.68230OpenAlexW2120092168MaRDI QIDQ2998728

Marcella Anselmo, Marina Madonia

Publication date: 10 May 2011

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/193071

zbMATH Keywords

two-dimensional languagescomplementunambiguity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items (3)

Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages ⋮ Two-dimensional models ⋮ Communication complexity tools on recognizable picture languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound technique for the size of nondeterministic finite automata
• Deterministic and unambiguous two-dimensional languages over one-letter alphabet
• Characterizations of recognizable picture series
• Intersection and union of regular languages and state complexity
• Nondeterminism versus determinism of finite automata over directed acyclic graphs
• Communication complexity method for measuring nondeterminism in finite automata
• Snake-Deterministic Tiling Systems
• Unambiguous recognizable two-dimensional 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
• A Note on Unambiguity, Finite Ambiguity and Complementation in Recognizable Two-Dimensional Languages
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures

This page was built for publication: Classes of two-dimensional languages and recognizability conditions