A Note on Ordinal DFAs

Details A Note on Ordinal DFAs A Note on Ordinal DFAs

2010-05-13

arxiv.org/abs/1005.2329v1

Computer Science

Formal Languages and Automata Theory

15 pages

Scientific paper

We prove the following theorem. Suppose that $M$ is a trim DFA on the Boolean alphabet $0,1$. The language $\L(M)$ is well-ordered by the lexicographic order $\slex$ iff whenever the non sink states $q,q.0$ are in the same strong component, then $q.1$ is a sink. It is easy to see that this property is sufficient. In order to show the necessity, we analyze the behavior of a $\slex$-descending sequence of words. This property is used to obtain a polynomial time algorithm to determine, given a DFA $M$, whether $\L(M)$ is well-ordered by the lexicographic order. Last, we apply an argument in \cite{BE,BEa} to give a proof that the least nonregular ordinal is $\omega^\omega $.

Affiliated with

Also associated with

No associations

Rating

A Note on Ordinal DFAs 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 A Note on Ordinal DFAs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Note on Ordinal DFAs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-640723