Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDFAs and PFAs with Long Shortest Synchronizing Word Length
71
0
0.0
(
0
)
Added by
Henk Don
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
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 show that every D3-directing CNFA can be mapped uniquely to a DFA with the same synchronizing word length. This implies that v{C}ernys conjecture generalizes to CNFAs and that the general upper bound for the length of a shortest D3-directing word is equal to the Pin-Frankl bound for DFAs. As a second consequence, for several classes of CNFAs sharper bounds are established. Finally, our results allow us to detect all critical CNFAs on at most 6 states. It turns out that only very few critical CNFAs exist.
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.
Given a finite group with a generating subset there is a well-established notion of length for a group element given in terms of its minimal length expression as a product of elements from the generating set. Recently, certain quantities called $lambda_{1}$ and $lambda_{2}$ have been defined that allow for a precise measure of how stable a group is under certain types of small perturbations in the generating expressions for the elements of the group. These quantities provide a means to measure differences among all possible paths in a Cayley graph for a group, establish a group theoretic analog for the notion of stability in nonlinear dynamical systems, and play an important role in the application of groups to computational genomics. In this paper, we further expose the fundamental properties of $lambda_{1}$ and $lambda_{2}$ by establishing their bounds when the underlying group is a dihedral group. An essential step in our approach is to completely characterize so-called symmetric presentations of the dihedral groups, providing insight into the manner in which $lambda_{1}$ and $lambda_{2}$ interact with finite group presentations. This is of interest independent of the study of the quantities $lambda_{1},; lambda_{2}$. Finally, we discuss several conjectures and open questions for future consideration.
We consider the class of groups whose word problem is poly-context-free; that is, an intersection of finitely many context-free languages. We show that any group which is virtually a finitely generated subgroup of a direct product of free groups has poly-context-free word problem, and conjecture that the converse also holds. We prove our conjecture for several classes of soluble groups, including metabelian groups and torsion-free soluble groups, and present progress towards resolving the conjecture for soluble groups in general. Some of the techniques introduced for proving languages not to be poly-context-free may be of independent interest.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
