1. A Note on Ordinal DFAs
- Author
-
Yi Di Zhang and Stephen L. Bloom
- Subjects
Combinatorics ,Discrete mathematics ,Sequence ,Algebra and Number Theory ,Deterministic finite automaton ,Computational Theory and Mathematics ,Order (ring theory) ,Component (group theory) ,Geometry and Topology ,Algebra over a field ,Lexicographical order ,Time complexity ,Mathematics - Abstract
We prove the following theorem. Suppose that M is a trim DFA. Then \(\mathcal{L}(M)\) is well-ordered by the lexicographic order < l 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 < l-descending sequence of words. This property is used to obtain a polynomial time algorithm to determine, given a DFA M, whether \(\mathcal{L}(M)\) is well-ordered by the lexicographic order. Last, we apply an argument in Bloom and Esik (Fundam Inform 99:383–407, 2010, Int J Found Comput Sci, 2011) to give a proof that the least nonregular ordinal is ωω.
- Published
- 2011