(Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars

DOI10.1007/978-3-319-22360-5_21zbMath1465.68124OpenAlexW2294458207MaRDI QIDQ2947427

Daniel Průša

Publication date: 23 September 2015

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-22360-5_21

zbMATH Keywords

undecidabilitypicture languagesemptiness problemmulti-dimensional context-free grammars

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42)

Related Items (1)

Undecidability of the emptiness problem for context-free picture languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A unifying approach to picture grammars
• Three-dimensional connected pictures are not recognizable by finite-state acceptors
• Two-dimensional connected pictures are not recognizable by finite-state acceptors
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• Positively Prodigious Powers or How Dudeney Done It?
• Regular expressions and context-free grammars for picture languages
• Non-recursive Trade-offs between Two-Dimensional Automata and Grammars
• Picture languages with array rewriting rules

This page was built for publication: (Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars