Comparing necessary conditions for recognizability of two-dimensional languages

DOI10.1007/978-3-642-21493-6_5MaRDI QIDQ3014932zbMATH OpenOpenAlexFDO

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

lower bound techniques on NFAtwo-dimensional languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• A stronger recognizability condition for two-dimensional languages
• Classes of two-dimensional languages and recognizability conditions
• scientific article; zbMATH DE number 871248
• Tiling Recognizable Two-Dimensional Languages
• Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages

Cites work

• A computational model for tiling recognizable two-dimensional languages
• A lower bound technique for the size of nondeterministic finite automata
• Classes of two-dimensional languages and recognizability conditions
• Communication complexity method for measuring nondeterminism in finite automata
• Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages
• Deterministic and unambiguous two-dimensional languages over one-letter alphabet
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• scientific article; zbMATH DE number 5141495 (Why is no real title available?)
• scientific article; zbMATH DE number 1206599 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• Intersection and union of regular languages and state complexity
• Matrix-based complexity functions and recognizable picture languages
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Picture recognizability with automata based on Wang tiles
• The monadic quantifier alternation hierarchy over grids and graphs
• Tile rewriting grammars and picture languages
• Unambiguous recognizable two-dimensional languages

Cited in

(8)

• Two-dimensional connected pictures are not recognizable by finite-state acceptors
• Classes of two-dimensional languages and recognizability conditions
• On Some Classes of 2D Languages and Their Relations
• Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages
• On Complexity of Two Dimensional Languages Generated by Transducers
• scientific article; zbMATH DE number 871248 (Why is no real title available?)
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages
• A stronger recognizability condition for two-dimensional languages

This page was built for publication: Comparing necessary conditions for recognizability of two-dimensional languages

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