The generative capacity of block-synchronized context-free grammars

AbstractWe 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