A representation of trees by languages I

AbstractA tree can be represented by a language consisting of a suitable coding of its finite branches. We investigate this representation and derive a number of reductions between certain equivalence problems for context-free tree grammars and recursive program schemes and the (open) equivalence problem for DPDA's. This is the first part of this work: it is devoted to technical results on prefix-free languages and strict deterministic grammars. Application to context-free tree grammars will be published in the second part