Decidability of EDT0L structural equivalence

DOI10.1016/S0304-3975(01)00197-9zbMath1002.68083MaRDI QIDQ1605312

Kai Salomaa, Sheng Yu

Publication date: 15 July 2002

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

zbMATH Keywords

formal languagesparallel grammarstree pushdown automata

Mathematics Subject Classification ID

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

Cites Work

• Decidability of structural equivalence of E0L grammars
• Deterministic tree pushdown automata and monadic tree rewriting systems
• Defining families of trees with E0L grammars
• On the equivalence, containment, and covering problems for the regular and context-free languages
• IO and OI. I
• IO and OI. II
• Bracketed context-free languages
• Structural equivalence of context-free grammars
• Pushdown tree automata
• A study in parallel rewriting systems
• Parallel context-free languages
• Decomposition Theorems for Various Kinds of Languages Parallel in Nature
• Complexity of E0L structural equivalence
• Parallel context-free languages
• Parenthesis Grammars
• Nested Stack Automata
• A characterization of parenthesis languages
• Mappings and grammars on trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item