@inproceedings{a24ce8749fc4415f8f59e40e4235791d,
title = "A rank hierarchy for deterministic tree-walking transducers",
abstract = "In this paper two complexity measures are investigated for the class of deterministic tree-walking transducers. We show that, when a constant bound is imposed on the crossing number of these devices, the rank of the input tree language induces an infinite, non-collapsing hierarchy. Using this result we solve some language-theoretic questions that were left open in the literature. Our separation result can also be transferred to other classes in the family of finite copying parallel rewriting systems, since a weak equivalence relation holds between these classes and deterministic tree-walking transducers, even when the complexity measures above are bounded.",
author = "Owen Rambow and Giorgio Satta",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1994.; 19th Colloquium on Trees in Algebra and Programming, CAAP 1994 ; Conference date: 11-04-1994 Through 13-04-1994",
year = "1994",
doi = "10.1007/bfb0017490",
language = "English",
isbn = "9783540578796",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "308--321",
editor = "Sophie Tison",
booktitle = "Trees in Algebra and Programming - 19th International Colloquium CAAP 1994, Proceedings",
}