A Hierarchy of Deterministic Top-down Tree Transformations

dc.contributor.author Slutzki, Giora
dc.contributor.author Vagvolgyi, Sandor
dc.contributor.department Computer Science
dc.date 2018-02-13T23:10:27.000
dc.date.accessioned 2020-06-30T01:55:32Z
dc.date.available 2020-06-30T01:55:32Z
dc.date.issued 1993-04-13
dc.description.abstract <p>The classes DTA, DTT, DTT{DR}, and DTT{R} stand for the family of tree transductions induced by all deterministic top-down tree automata, deterministic top-down tree transducers, deterministic top-down tree transducers with deterministic top-down look-ahead, and deterministic top-down tree transducers with regular look-ahead, respectively. In this paper we study two hierarchies obtained by compositions of tree transformation classes and show that they are proper and that they ``shuffle perfectly''. Using these results we show that the problem of determining the correct inclusion relationship between two arbitrary compositions of tree transformation classes from the set M={ DTA, DTT, DTT{DR}, DTT{R} } can be decided in linear time.</p>
dc.identifier archive/lib.dr.iastate.edu/cs_techreports/171/
dc.identifier.articleid 1159
dc.identifier.contextkey 5407992
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath cs_techreports/171
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/19985
dc.source.bitstream archive/lib.dr.iastate.edu/cs_techreports/171/TR93_10a.pdf|||Fri Jan 14 21:15:58 UTC 2022
dc.subject.disciplines Theory and Algorithms
dc.title A Hierarchy of Deterministic Top-down Tree Transformations
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
File
Original bundle
Now showing 1 - 1 of 1
Name:
TR93_10a.pdf
Size:
313.58 KB
Format:
Adobe Portable Document Format
Description:
Collections