Computer Science – Formal Languages and Automata Theory
Scientific paper
2010-08-10
EPTCS 31, 2010, pp. 78-87
Computer Science
Formal Languages and Automata Theory
In Proceedings DCFS 2010, arXiv:1008.1270
Scientific paper
10.4204/EPTCS.31.10
It is known that an ordinal is the order type of the lexicographic ordering of a regular language if and only if it is less than omega^omega. We design a polynomial time algorithm that constructs, for each well-ordered regular language L with respect to the lexicographic ordering, given by a deterministic finite automaton, the Cantor Normal Form of its order type. It follows that there is a polynomial time algorithm to decide whether two deterministic finite automata accepting well-ordered regular languages accept isomorphic languages. We also give estimates on the size of the smallest automaton representing an ordinal less than omega^omega, together with an algorithm that translates each such ordinal to an automaton.
No associations
LandOfFree
Representing Small Ordinals by Finite 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 Representing Small Ordinals by Finite Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Representing Small Ordinals by Finite Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-583257