Printer Friendly

A note on a recent attempt to improve the Pin-Frankl bound.

This short note studies a problem related with synchronizing automata and Cerny's conjecture, formulated in [2]. A good survey on the topic is given in [10]. See [1], [4], [5] for recent work on the subject.

A (deterministic, finite state, complete) automaton (DFA) is a triplet (Q, [SIGMA], [delta]) with Q the set of states, [SIGMA] the alphabet of letters and S the transition function S : Q x E ^ Q defining the effect of the letters on the states. For [q.sub.i], [q.sub.j] [member of] Q and l [member of] [SIGMA], we write [q.sub.i]l = [q.sub.j] if [delta]([q.sub.i], l) = [q.sub.j]. We call a word w of length m a sequence of m letters [l.sub.1] ... [l.sub.m], [l.sub.i] [member of] [SIGMA], 1 [less than or equal to] i [less than or equal to] m. We write [[summation].sup.m] the set of words of length m. For [q.sub.i], [q.sub.j] [member of] Q and w = [l.sub.1] ... [l.sub.m] [member of] [[summation].sup.m], we write [q.sub.i]w = [q.sub.j] if [delta](... [delta]([delta]([q.sub.i], [l.sub.1]), [l.sub.2]) ..., [l.sub.m]) = [q.sub.j]. For an automaton with n states and a word w, we note Qw = {[q.sub.j] | [q.sub.i]w = [q.sub.j], 1 [less than or equal to] i [less than or equal to] n} the set of states that are in the image of w. We can represent an automaton as a directed graph. Each state is represented as a vertex, and the effect of each letter on each state is represented as a directed edge. We call a DFA strongly connected if its graph representation is a strongly connected graph.

A word w is called a synchronizing word if, for any states [q.sub.i], [q.sub.j] [member of] Q, [q.sub.i]w = [q.sub.j]w. A DFA is called a synchronizing automaton if it has a synchronizing word.

Cerny's conjecture [2] states that any synchronizing automaton with n states has a synchronizing word of length at most [(n - 1).sup.2].

So far the best proven bound is ([n.sup.3] - n)/6, obtained more than 30 years ago in [3] and [7], and rediscovered independently in [6]. Recently, a tentative improvement to n(7[n.sup.2] + 6n - 16)/48 has been proposed in [8]. However, as mentioned later by the author on ArXiv [9], there is a flaw in the proof. Nevertheless, since the publication of [8], many new papers are citing this result, and no publication clearly confirms that the proof is not valid. In this note, we make this point clear by providing a counterexample to Lemma 3 in [8]. The lemma is the following:

Lemma 1 (Lemma 3 in [8]) Let Q be the set of states of a synchronizing strongly connected n-state DFA. Then for any state q there exists a word w of length not greater than n such that q [not member of] Qw. For any k < n there are at least k states [q.sub.1], ..., [q.sub.k] and words [w.sub.1], ..., [w.sub.k] of length not greater than k such that [q.sub.i] [not member of] Q[w.sub.i], 1 [less than or equal to] i [less than or equal to] k.

We refute the lemma by exhibiting an automaton such that, for one state [q.sub.0], there is no word w of length smaller than or equal to the number of states with the property that [q.sub.0] [not member of] Qw.

Counterexample The automaton represented in Fig. 1 is a synchronizing automaton, as the word abbababba is a synchronizing word. However, the shortest word w such that [q.sub.0] [not member of] Qw is w = abbaba. Since the automaton has only 4 states and w is 6 letters long, this contradicts Lemma 1.

Lemma 1 was a key step in the improvement on the maximal length of a shortest synchronizing word. We observe that a weaker version of Lemma 1 could still improve the Pin-Frankl bound. In fact, any value proportional to the number of states of the automaton would lead to an improvement of the bound. This motivates us to raise the following open question.

Open question Let Q be the set of states of a synchronizing strongly connected n-state DFA.

Is there a constant c such that, for any state q [member of] Q, there exists a word w of length not greater than cn such that q [not member of] Qw ?

References

[1] V. Blondel, R. M. Jungers, and A. Olshevsky. On primitivity of sets of matrices. ArXiv preprint. http://arxiv.org/abs/1306.0729, 2014.

[2] J. Cerny. Pozndmka k homogennym eksperimentom s konecnymi automatami. Matematicko-fysikalny Casopis SAV, 14:208-216, 1964.

[3] P. Frankl. An extremal problem for two families of sets. European Journal of Combinatorics, 3:125-127, 1982.

[4] F. Gonze and R. M. Jungers. On the synchronizing probability function and the triple rendezvous time for synchronzing automata. ArXiv preprint. http://arxiv.org/abs/1410.4034, 2014.

[5] R. M. Jungers. The synchronizing probability function of an automaton. SIAM Journal on Discrete Mathematics, 26(1):177-192, 2012.

[6] A. A. Klyachko, I. K. Rystsov, and Spivak M. A. An extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton. Kibernetika, 2:16-20, 1987. in Russian; Engl. translation: Cybernetics 23 (1987) 165-171.

[7] J.-E. Pin. On two combinatorial problems arising from automata theory. Annals of Discrete Mathematics, 17:535-548, 1983.

[8] A. N. Trahtman. Modifying the upper bound on the length of minimal synchronizing word. In FCT 2011, volume 6914 of Lecture Notes in Computer Science, pages 173-180. Springer-Verlag, 2011.

[9] A. N. Trahtman. Modifying the upper bound on the length of minimal synchronizing word. ArXiv preprint. http://arxiv.org/abs/1104.2409, 2011.

[10] M. V. Volkov. Synchronizing automata and the Cerny conjecture. In LATA 2008, volume 5196 of Lecture Notes in Computer Science, pages 11-27. Springer-Verlag, 2008.

Francois Gonze (1) Raphael M. Jungers (1) ([dagger]) Avraham N. Trahtman (2)

(1) ICTEAM Institute, UCLouvain, Louvain La Neuve, Belgium

(2) Dep. of Math., Bar-Ilan University, Ramat Gan, Israel

* This work was also supported by the communaute francaise de Belgique - Actions de Recherche Concertees and by the Belgian Program on Interuniversity Attraction Poles initiated by the Belgian Federal Science Policy Office. Emails: francois.gonze@uclouvain.be, raphael.jungers@uclouvain.be, trakht@macs.biu.ac.il

([dagger]) R. M. Jungers is a F.R.S.-FNRS Research Associate.

received 3rd Dec. 2014, revised 2nd Apr. 2015, 8th Apr. 2015, accepted 8th Apr. 2015.
COPYRIGHT 2015 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Gonze, Francois; Jungers, Raphael M.; Trahtman, Avraham N.
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Date:Jan 1, 2015
Words:1133
Previous Article:Parameterized complexity of synchronization and road coloring.
Next Article:On the Hausdorff measure of regular [omega]-languages in cantor space.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters