Completeness results concerning systolic tree automata and E0L languages

DOI10.1016/0020-0190(94)00170-4zbMath0875.68528MaRDI QIDQ674289

Alessandro Roncato, Angelo Monti

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00170-4

zbMATH Keywords

Computational complexity; PSPACE-completeness; Formal languages; E0L; Tree automata

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

Related Items

Succinctness of descriptions of SBTA-languages, Decision procedures for inductive Boolean functions based on alternating automata, Systolic tree \(\omega\)-languages: The operational and the logical view, A note on emptiness for alternating finite automata with a one-letter alphabet

Cites Work

• On a family of L languages resulting from systolic tree automata
• Synthesis, structure and power of systolic computations
• A characterization of systolic binary tree automata and applications
• Systolic automata for VLSI on balanced trees
• A Kleene-like characterization of languages accepted by systolic tree automata
• Non acceptability criteria and closure properties for the class of languages accepted by binary systolic tree automata
• Complexity of some problems concerningL systems
• Description of developmental languages using recurrence systems
• On a family of acceptors for some classes of developmental languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item