Decidability of structural equivalence of E0L grammars

DOI10.1016/0304-3975(91)90176-3MaRDI QIDQ807023zbMATH OpenOpenAlexFDO

Authors Kai Salomaa, Sheng Yu

Publication date 1991

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

Full work available at URL https://doi.org/10.1016/0304-3975(91)90176-3

zbMATH Keywords

EOL grammarsstructural equivalence

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Review text

Two EOL grammars are said to be structurally equivalent if they generate the same sets of teminal syntax trees when one disregards the nonterminals labeling the internal nodes of the trees. The authors prove that the structural equivalence of EOL grammars is decidable, thus solving an open problem posed by T. Ottmann and D. Wood [Structural equivalence of EOL grammars, Research Report CS-89-40, Univ. of Waterloo (1989)]. The proof is based on the use of so-called height-counting tree automata which are finite bottom-up tree automata that remember the heights of the subtrees processed so far.

Recommendations

• Theory Is Forever
• scientific article; zbMATH DE number 522868
• scientific article; zbMATH DE number 1222112
• Structural equivalence and ET0L grammars
• scientific article; zbMATH DE number 176929

Cites work

• Bracketed context-free languages
• Defining families of trees with E0L grammars
• scientific article; zbMATH DE number 176930 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 194974 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Indexed Grammars—An Extension of Context-Free Grammars
• Parenthesis Grammars
• Structural equivalence of context-free grammars

Cited in

(17)

• Defining families of trees with E0L grammars
• Decidability of EDT0L structural equivalence
• The strong equivalence of ET0L grammars
• 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 1222112 (Why is no real title available?)
• scientific article; zbMATH DE number 522868 (Why is no real title available?)
• Complexity of E0L structural equivalence
• scientific article; zbMATH DE number 1159716 (Why is no real title available?)
• scientific article; zbMATH DE number 3999316 (Why is no real title available?)
• Machine characterization of terminal weighted eol languages
• Complexity of E0L structural equivalence
• Theory Is Forever
• On elimination of erasing rules from E0S grammars
• Structural equivalence and ET0L grammars
• Decidability of equivalence for deterministic synchronized tree automata

This page was built for publication: Decidability of structural equivalence of E0L grammars

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