Complexity of EOL structural equivalence

DOI10.1007/3-540-58338-6_105zbMath1493.68162OpenAlexW1545886122MaRDI QIDQ5096917

Kai Salomaa, Derick Wood, Sheng Yu

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58338-6_105

Mathematics Subject Classification ID

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

Cites Work

• Decidability of structural equivalence of E0L grammars
• On the power of synchronization in parallel computations
• Defining families of trees with E0L grammars
• Communication for alternating machines
• The membership question for ETOL-languages is polynomially complete
• The tape-complexity of context-independent developmental languages
• Structural equivalence of context-free grammars
• Deciding Equivalence of Finite Tree Automata
• Complexity of some problems concerningL systems
• Parenthesis Grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of EOL structural equivalence