Back to Search Start Over

Branching synchronization grammars with nested tables

Authors :
Joost Engelfriet
Frank Drewes
Source :
Journal of Computer and System Sciences. (3):611-656
Publisher :
Elsevier Inc.

Abstract

A generalization of ET0L systems is introduced: grammars with branching synchronization and nested tables. The main result is that branching synchronization grammars with tables of nesting depth n have the same string- and tree-generating power as n-fold compositions of top-down tree transducers. Based on this it is shown, e.g., that the family of generated string languages is a full principal AFL for each n.

Details

Language :
English
ISSN :
00220000
Issue :
3
Database :
OpenAIRE
Journal :
Journal of Computer and System Sciences
Accession number :
edsair.doi.dedup.....144c0b8adf9c784c3877a39c4f76bffb
Full Text :
https://doi.org/10.1016/j.jcss.2003.10.001