Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages

DOI10.1007/978-3-642-21493-6_5zbMath1307.68044OpenAlexW140044370MaRDI QIDQ3014932

Marcella Anselmo, Marina Madonia

Publication date: 8 July 2011

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

Full work available at URL: https://doi.org/10.1007/978-3-642-21493-6_5

zbMATH Keywords

two-dimensional languageslower bound techniques on NFA

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound technique for the size of nondeterministic finite automata
• A computational model for tiling recognizable two-dimensional languages
• Deterministic and unambiguous two-dimensional languages over one-letter alphabet
• Intersection and union of regular languages and state complexity
• Communication complexity method for measuring nondeterminism in finite automata
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Tile rewriting grammars and picture languages
• The monadic quantifier alternation hierarchy over grids and graphs
• Classes of two-dimensional languages and recognizability conditions
• Picture Recognizability with Automata Based on Wang Tiles
• Unambiguous recognizable two-dimensional languages
• Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard

This page was built for publication: Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages