Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Note on Ordinal DFAs
179
0
0.0
(
0
)
Added by
Stephen Bloom
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 $.
rate research
Read More
We compute all synchronizing DFAs with 7 states and synchronization length >= 29. Furthermore, we compute alphabet size ranges for maximal, minimal and semi-minimal synchronizing DFAs with up to 7 states.
In this paper, we consider the transition complexity of regular languages based on the incomplete deterministic finite automata. A number of results on Boolean operations have been obtained. It is shown that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity result is similar to that of state complexity.
This paper contains results which arose from the research which led to arXiv:1801.10436, but which did not fit in arXiv:1801.10436. So arXiv:1801.10436 contains the highlight results, but there are more results which are interesting enough to be shared.
The purposes of this note are the following two; we first generalize Okada-Takeutis well quasi ordinal diagram theory, utilizing the recent result of Dershowitz-Tzamerets version of tree embedding theorem with gap conditions. Second, we discuss possible use of such strong ordinal notation systems for the purpose of a typical traditional termination proof method for term rewriting systems, especially for second-order (pattern-matching-based) rewriting systems including a rewrite-theoretic version of Buchholzs hydra game.
This is an auxiliary note to [12]. To be precise, here we have gathered the proofs of all the statements in [12, Section 5] that happen to have points of contact with techniques recently developed in Chousionis-Pratt [5] and Chunaev [6].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
