Context-free tree grammars are as powerful as context-free jungle grammars

Frank Drewes; Joost Engelfriet

doi:10.14232/actacyb.22.2.2015.9

Context-free tree grammars are as powerful as context-free jungle grammars

Authors

Frank Drewes
Joost Engelfriet

DOI:

https://doi.org/10.14232/actacyb.22.2.2015.9

Abstract

Jungles generalize trees by sharing subtrees and allowing garbage. It is shown that IO context-free tree grammars generate the same jungle languages as context-free jungle grammars. Also, they define the same subsets of any algebra.

Downloads

Published

2015-01-01

How to Cite

Drewes, F., & Engelfriet, J. (2015). Context-free tree grammars are as powerful as context-free jungle grammars. Acta Cybernetica, 22(2), 373–392. https://doi.org/10.14232/actacyb.22.2.2015.9