Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSubset synchronization of DFAs and PFAs, and some other results
67
0
0.0
(
0
)
Added by
Michiel de Bondt
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Michiel de Bondt
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We study extremal and algorithmic questions of subset and careful synchronization in monotonic automata. We show that several synchronization problems that are hard in general automata can be solved in polynomial time in monotonic automata, even without knowing a linear order of the states preserved by the transitions. We provide asymptotically tight bounds on the maximum length of a shortest word synchronizing a subset of states in a monotonic automaton and a shortest word carefully synchronizing a partial monotonic automaton. We provide a complexity framework for dealing with problems for monotonic weakly acyclic automata over a three-letter alphabet, and use it to prove NP-completeness and inapproximability of problems such as {sc Finite Automata Intersection} and the problem of computing the rank of a subset of states in this class. We also show that checking whether a monotonic partial automaton over a four-letter alphabet is carefully synchronizing is NP-hard. Finally, we give a simple necessary and sufficient condition when a strongly connected digraph with a selected subset of vertices can be transformed into a deterministic automaton where the corresponding subset of states is synchronizing.
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.
It was conjectured by v{C}erny in 1964, that a synchronizing DFA on $n$ states always has a shortest synchronizing word of length at most $(n-1)^2$, and he gave a sequence of DFAs for which this bound is reached. Until now a full analysis of all DFAs reaching this bound was only given for $n leq 4$, and with bounds on the number of symbols for $n leq 10$. Here we give the full analysis for $n leq 6$, without bounds on the number of symbols. For PFAs the bound is much higher. For $n leq 6$ we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding $(n-1)^2$ for $n =4,5,6$. For arbitrary n we give a construction of a PFA on three symbols with exponential shortest synchronizing word length, giving significantly better bounds than earlier exponential constructions. We give a transformation of this PFA to a PFA on two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation.
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.
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 $.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
