Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657854 | Theoretical Computer Science | 2005 | 15 Pages |
Abstract
We consider the yield languages of synchronized tree automata, called the synchronized context-free (SCF) languages. We show that their language family coincides with the family of ET0L languages using both studied types of synchronization. Furthermore, we examine a generalization of SCF grammars, the block-synchronized context-free (BSCF) grammars and determine that their generated language family is equal to that of the indexed languages using the same two types of synchronization. However, when the nesting depth of BSCF grammars is bounded above by some constant, the generated language family is also equal to the family of ET0L languages. This shows that the unbounded nesting depth language family is strictly larger than the bounded nesting depth family, as previously conjectured.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
I. McQuillan,