Article ID Journal Published Year Pages File Type
9657854 Theoretical Computer Science 2005 15 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,