Tree transducers, L systems, and two-way machines

Share/Save/Bookmark

Engelfriet, Joost and Rozenberg, Grzegorz and Slutzki, Giora (1980) Tree transducers, L systems, and two-way machines. Journal of Computer and System Sciences, 20 (2). pp. 150-202. ISSN 0022-0000

open access
[img]
Preview
PDF
3MB
Abstract:A relationship between parallel rewriting systems and two-way machines is investigated. Restrictions on the “copying power” of these devices endow them with rich structuring and give insight into the issues of determinism, parallelism, and copying. Among the parallel rewriting systems considered are the top-down tree transducer; the generalized syntax-directed translation scheme and the ETOL system, and among the two-way machines are the tree-walking automaton, the two-way finite-state transducer, and (generalizations of) the one-way checking stack automaton. The. relationship of these devices to macro grammars is also considered. An effort is made .to provide a systematic survey of a number of existing results.
Item Type:Article
Copyright:© 1980 Elsevier Science
Link to this item:http://purl.utwente.nl/publications/68486
Official URL:http://dx.doi.org/10.1016/0022-0000(80)90058-6
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page