Complexity of E0L structural equivalence

DOI10.1051/ITA/1995290604711MaRDI QIDQ4359286zbMATHOpenAlexFDO

Authors Kai Salomaa, D. Wood, Sheng Yu

Publication date 8 October 1997

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92519

zbMATH Keywords

E0L structural equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Complexity of E0L structural equivalence
• Decidability of structural equivalence of E0L grammars
• scientific article; zbMATH DE number 176930
• Theory Is Forever

Cites work

• scientific article; zbMATH DE number 4130026 (Why is no real title available?)
• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 17800 (Why is no real title available?)
• scientific article; zbMATH DE number 176929 (Why is no real title available?)
• scientific article; zbMATH DE number 176930 (Why is no real title available?)
• scientific article; zbMATH DE number 176931 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 522868 (Why is no real title available?)
• scientific article; zbMATH DE number 194974 (Why is no real title available?)
• scientific article; zbMATH DE number 3802813 (Why is no real title available?)
• Alternation
• Communication for alternating machines
• Complexity of some problems concerningL systems
• Decidability of structural equivalence of E0L grammars
• Deciding Equivalence of Finite Tree Automata
• Defining families of trees with E0L grammars
• Deterministic versus nondeterministic space in terms of synchronized alternating machines
• On the power of synchronization in parallel computations
• Parenthesis Grammars
• Structural equivalence of context-free grammars
• The membership question for ETOL-languages is polynomially complete
• The tape-complexity of context-independent developmental languages

Cited in

(7)

• scientific article; zbMATH DE number 176930 (Why is no real title available?)
• Complexity of E0L structural equivalence
• Decidability of EDT0L structural equivalence
• scientific article; zbMATH DE number 176240 (Why is no real title available?)
• Structural equivalence and ET0L grammars
• scientific article; zbMATH DE number 4085027 (Why is no real title available?)
• scientific article; zbMATH DE number 176931 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4359286)