Isomorphism of regular trees and words

Details Isomorphism of regular trees and words Isomorphism of regular trees and words

2011-02-14

arxiv.org/abs/1102.2782v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

The computational complexity of the isomorphism problem for regular trees, regular linear orders, and regular words is analyzed. A tree is regular if it is isomorphic to the prefix order on a regular language. In case regular languages are represented by NFAs (DFAs), the isomorphism problem for regular trees turns out to be EXPTIME-complete (resp. P-complete). In case the input automata are acyclic NFAs (acyclic DFAs), the corresponding trees are (succinctly represented) finite trees, and the isomorphism problem turns out to be PSPACE-complete (resp. P-complete). A linear order is regular if it is isomorphic to the lexicographic order on a regular language. A polynomial time algorithm for the isomorphism problem for regular linear orders (and even regular words, which generalize the latter) given by DFAs is presented. This solves an open problem by Esik and Bloom.

Affiliated with

Also associated with

No associations

Rating

Isomorphism of regular trees and words 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 Isomorphism of regular trees and words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Isomorphism of regular trees and words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-216050