Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

The copying power of one-state tree transducers

Share/Save/Bookmark

Engelfriet, Joost and Skyum, Sven (1982) The copying power of one-state tree transducers. Journal of Computer and System Sciences, 25 (3). pp. 418-435. ISSN 0022-0000

[img]
Preview
PDF
1170Kb
Abstract:One-state deterministic top-down tree transducers (or, tree homomorphisms) cannot handle "prime copying," i.e., their class of output (string) languages is not closed under the operation L → {$(w$)f(n) w ε L, f(n) ≥ 1}, where f is any integer function whose range contains numbers with arbitrarily large prime factors (such as a polynomial). The exact amount of nonclosure under these copying operations is established for several classes of input (tree) languages. These results are relevant to the extended definable (or, restricted parallel level) languages, to the syntax-directed translation of context-free languages, and to the tree transducer hierarchy.

Item Type:Article
Copyright:© 1982 Elsevier Science
Link to this item:http://purl.utwente.nl/publications/69024
Official URL:http://dx.doi.org/10.1016/0022-0000(82)90019-8
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page