Completeness results concerning systolic tree automata and E0L languages

DOI10.1016/0020-0190(94)00170-4zbMath0875.68528OpenAlexW2091862052MaRDI 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 complexityPSPACE-completenessFormal languagesE0LTree automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (4)

A note on emptiness for alternating finite automata with a one-letter alphabet ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Completeness results concerning systolic tree automata and E0L languages