The generative capacity of block-synchronized context-free grammars

摘要

We consider the yield languages of synchronized tree automata, called the synchronized contextfree (SCF) languages. We show that their language family coincides with the family of ETOL 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 ETOL languages. This shows that the unbounded nesting depth language family is strictly larger than the bounded nesting depth family, as previously conjectured. (c) 2004 Elsevier B.V. All rights reserved.