Back to Search
Start Over
Branching synchronization grammars with nested tables
- 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.
- Subjects :
- Combinatorics
Branching (linguistics)
Tree-adjoining grammar
Discrete mathematics
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Rule-based machine translation
Computational Theory and Mathematics
Computer Networks and Communications
Applied Mathematics
Tree transducers
L-attributed grammar
Mathematics
Theoretical Computer Science
Subjects
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