Non-recursive trade-offs between two-dimensional automata and grammars

DOI10.1016/j.tcs.2015.05.033zbMath1332.68127OpenAlexW2173593318MaRDI QIDQ896688

Daniel Průša

Publication date: 10 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.05.033

zbMATH Keywords

picture languagesdescriptional complexityfour-way automatanon-recursive trade-offstwo-dimensional context-free grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

Unnamed Item ⋮ Simple picture processing based on finite automata and regular grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A unifying approach to picture grammars
• A note on three-way two dimensional alternating Turing machines
• Some properties of two-dimensional on-line tessellation acceptors
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• 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.
• On Measuring Non-Recursive Trade-Offs
• A note on the succinctness of descriptions of deterministic languages
• On Non-Computable Functions
• Regular expressions and context-free grammars for picture languages
• ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA
• Picture languages with array rewriting rules
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
• Theory Is Forever