Properties of quasi-alphabetic tree bimorphisms

Details Properties of quasi-alphabetic tree bimorphisms Properties of quasi-alphabetic tree bimorphisms

2009-06-12

arxiv.org/abs/0906.2369v1

Computer Science

Computation and Language

15 pages, 1 figure

Scientific paper

We study the class of quasi-alphabetic relations, i.e., tree transformations defined by tree bimorphisms with two quasi-alphabetic tree homomorphisms and a regular tree language. We present a canonical representation of these relations; as an immediate consequence, we get the closure under union. Also, we show that they are not closed under intersection and complement, and do not preserve most common operations on trees (branches, subtrees, v-product, v-quotient, f-top-catenation). Moreover, we prove that the translations defined by quasi-alphabetic tree bimorphism are exactly products of context-free string languages. We conclude by presenting the connections between quasi-alphabetic relations, alphabetic relations and classes of tree transformations defined by several types of top-down tree transducers. Furthermore, we get that quasi-alphabetic relations preserve the recognizable and algebraic tree languages.

Affiliated with

Also associated with

No associations

Rating

Properties of quasi-alphabetic tree bimorphisms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Properties of quasi-alphabetic tree bimorphisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Properties of quasi-alphabetic tree bimorphisms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-138571