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

Drewes, Frank and Engelfriet, Joost: Context-free tree grammars are as powerful as context-free jungle grammars. Acta cybernetica, (22) 2. pp. 373-392. (2015)

[img] Cikk, tanulmány, mű
actacyb_22_2_2015_9.pdf

Download (441kB)

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.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2015
Volume: 22
Number: 2
Page Range: pp. 373-392
ISSN: 0324-721X
Language: angol
DOI: https://doi.org/10.14232/actacyb.22.2.2015.9
Uncontrolled Keywords: Matematikai nyelvészet
Additional Information: Bibliogr.: p. 390-392.
Date Deposited: 2016. Oct. 17. 10:36
Last Modified: 2018. Jun. 06. 18:48
URI: http://acta.bibl.u-szeged.hu/id/eprint/36210

Actions (login required)

View Item View Item