Top

Published in:

2021 | OriginalPaper | Chapter

State Complexity of the Set of Synchronizing Words for Circular Automata and Automata over Binary Alphabets

Author : Stefan Hoffmann

Published in: Language and Automata Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Most slowly synchronizing automata over binary alphabets are circular, i.e., containing a letter permuting the states in a single cycle, and their set of synchronizing words has maximal state complexity, which also implies complete reachability. Here, we take a closer look at generalized circular and completely reachable automata. We derive that over a binary alphabet every completely reachable automaton must be circular, a consequence of a structural result stating that completely reachable automata over strictly less letters than states always contain permutational letters. We state sufficient conditions for the state complexity of the set of synchronizing words of a generalized circular automaton to be maximal. We apply our main criteria to the family \(\mathscr {K}_n\) of automata that was previously only conjectured to have this property.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words

next chapter Cadences in Grammar-Compressed Strings

The circular automata are a proper subfamily of the generalized circular automata, as shown by \(\mathscr {A} = (\{a,b\}, [3], \delta )\) with \(\delta (0, a) = 1, \delta (1, a) = 0, \delta (2,a) = 2\) and \(\delta (0, b) = 0, \delta (1, b) = 2, \delta (2, b) = 1\). The word ba cyclically permutes the states.

For, if we choose a finite number of words and build the automaton by identifying these words with new letters, distinguishability or reachability of states (or subsets of states) of this new automaton is inherited to the original automaton. Hence, all results are also valid when stated with words instead of letters, but otherwise the same conditions.

Note that \(0< m < n\) implies \(\delta (q, b^m) \ne q\). Also note that we added n on the right hand side to account for values \(d > 1\). In Proposition 10 we only subtract one from the exponent of b, which is always non-zero and strictly smaller than n, and so we do not needed this “correction for the b-cycle” in case of resulting negative exponents.

Note that here, even if the bounds for m from Theorem 8 do not include this case, \(\delta (q, w) = \delta (q, b^nw) = \delta (q, wb^{n-1})\), which is equivalent with \(\delta (q, w) = \delta (q, b)\).

I slightly changed the numbering of the states with respect to the action of the letter a compared to [13].

Ananichev, D., Gusev, V., Volkov, M.: Slowly synchronizing automata and digraphs. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 55–65. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15155-2_7CrossRef

Ananichev, D.S., Volkov, M.V., Gusev, V.V.: Primitive digraphs with large exponents and slowly synchronizing automata. J. Math. Sci. 192(3), 263–278 (2013)MathSciNetCrossRef

Bondar, E.A., Volkov, M.V.: Completely reachable automata. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol. 9777, pp. 1–17. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-41114-9_1CrossRef

Bondar, E.A., Volkov, M.V.: A characterization of completely reachable automata. In: Hoshi, M., Seki, S. (eds.) DLT 2018. LNCS, vol. 11088, pp. 145–155. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98654-8_12CrossRef

Černý, J.: Poznámka k homogénnym experimentom s konečnými automatmi. Matematicko-fyzikálny časopis 14(3), 208–216 (1964)

Don, H.: The Černý conjecture and 1-contracting automata. Electron. J. Comb. 23(3), P3.12 (2016)MathSciNetCrossRef

Dubuc, L.: Les automates circulaires biaisés vérifient la conjecture de Cerný. ITA 30(6), 495–505 (1996)MATH

Dubuc, L.: Sur les automates circulaires et la conjecture de Cerný. ITA 32(1–3), 21–34 (1998)

Gonze, F., Jungers, R.M.: Hardly reachable subsets and completely reachable automata with 1-deficient words. J. Automata Lang. Comb. 24(2–4), 321–342 (2019)MathSciNetMATH

10.

Hoffmann, S.: Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words. In: Leporati, A., et al. (eds.) LATA 2021. LNCS, vol. 12638, pp. 305–317. Springer, Cham (2021)

11.

Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, Boston (1979)MATH

12.

Maslennikova, M.I.: Reset complexity of ideal languages. CoRR abs/1404.2816 (2014)

13.

Maslennikova, M.I.: Reset complexity of ideal languages over a binary alphabet. Int. J. Found. Comput. Sci. 30(6–7), 1177–1196 (2019)MathSciNetCrossRef

14.

Pin, J.E.: Sur un cas particulier de la conjecture de Cerny. In: Ausiello, G., Böhm, C. (eds.) ICALP 1978. LNCS, vol. 62, pp. 345–352. Springer, Heidelberg (1978). https://doi.org/10.1007/3-540-08860-1_25CrossRef

15.

Sandberg, S.: 1 Homing and synchronizing sequences. In: Broy, M., Jonsson, B., Katoen, J.-P., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive Systems. LNCS, vol. 3472, pp. 5–33. Springer, Heidelberg (2005). https://doi.org/10.1007/11498490_2CrossRef

16.

Starke, P.H.: Eine Bemerkung über homogene Experimente. Elektronische Informationsverarbeitung und Kybernetik (later J. Inf. Process. Cybern.) 2(4), 257–259 (1966)MATH

17.

Volkov, M.V.: Synchronizing automata and the Černý conjecture. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 11–27. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88282-4_4CrossRef

Title: State Complexity of the Set of Synchronizing Words for Circular Automata and Automata over Binary Alphabets
Author: Stefan Hoffmann
Publisher: Springer International Publishing
Book: Language and Automata Theory and Applications
Print ISBN: 978-3-030-68194-4

Electronic ISBN: 978-3-030-68195-1

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-68195-1_25

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner