Representing Small Ordinals by Finite Automata

Computer Science – Formal Languages and Automata Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-583257

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.