Representing Small Ordinals by Finite Automata

Zoltan Ésik
(University of Szeged)

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.

In Ian McQuillan and Giovanni Pighizzini: Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (DCFS 2010), Saskatoon, Canada, 8-10th August 2010, Electronic Proceedings in Theoretical Computer Science 31, pp. 78–87.
Published: 7th August 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.31.10 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org