Transformations Between Different Types of Unranked Bottom-Up Tree Automata

Details Transformations Between Different Types of Unranked Bottom-Up Tree Automata Transformations Between Different Types of Unranked Bottom-Up Tree Automata

2010-08-10

arxiv.org/abs/1008.1658v1

EPTCS 31, 2010, pp. 159-168

Computer Science

Formal Languages and Automata Theory

In Proceedings DCFS 2010, arXiv:1008.1270

Scientific paper

10.4204/EPTCS.31.18

We consider the representational state complexity of unranked tree automata. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by a DFA or an NFA. Also, we consider for unranked tree automata the alternative syntactic definition of determinism introduced by Cristau et al. (FCT'05, Lect. Notes Comput. Sci. 3623, pp. 68-79). We establish upper and lower bounds for the state complexity of conversions between different types of unranked tree automata.

Affiliated with

Also associated with

No associations

Rating

Transformations Between Different Types of Unranked Bottom-Up Tree Automata 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 Transformations Between Different Types of Unranked Bottom-Up Tree Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transformations Between Different Types of Unranked Bottom-Up Tree Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-583288