Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Acta Informatica
Published in: Acta Informatica 4/2022

22-07-2022 | Original Article

Careful synchronization of partial deterministic finite automata

Authors: Hanan Shabana, M. V. Volkov

Published in: Acta Informatica | Issue 4/2022

Log in

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

search-config
loading …

Abstract

We approach the task of computing a carefully synchronizing word of minimum length for a given partial deterministic automaton, encoding the problem as an instance of SAT and invoking a SAT solver. Our experiments demonstrate that this approach gives satisfactory results for automata with up to 100 states even if very modest computational resources are used. We compare our results with the ones obtained by the first author for exact synchronization, which is another version of synchronization studied in the literature, and draw some theoretical conclusions.
previous article Lamplighter groups and automata
next article On the decidability of finding a positive ILP-instance in a regular set of ILP-instances

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 "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

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
Footnotes
1
It should be mentioned that Rystsov [30] used the term ‘synchronizing word’ for what we call ‘carefully synchronizing word’, following Martyugin [20‐24]. The authors are grateful to Dr. Pavel Panteleev who drew their attention to Rystsov’s paper.
 
2
We refer the reader to [5,  Chapters 3 and 10] for a detailed account of profound connections between codes and automata.
 
3
It is fair to say that encodings in [33, 35] were designed to handle much more general nondeterministic automata so it is not a surprise that those encodings were bulkier than the present one.
 
4
Türker [40] uses the term ‘reset sequence’ for what we call ‘exactly synchronizing word’.
 
Literature
1.
Ananichev, D.S., Volkov, M.V.: Some results on Černý type problems for transformation semigroups. In: Araújo, I. M., Branco, M.J.J., Fernandes, V.H., Gomes, G.M.S. (eds.) Semigroups and Languages, pp. 23–42. World Scientific (2004)
2.
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
3.
Berlinkov, M.V.: On two algorithmic problems about synchronizing automata. In: Shur, A.M., Volkov, M.V. (eds.) Developments in Language Theory. 18th International Conference, DLT 2014. LNCS, 8633, 61–67. Springer (2014)
4.
Berlinkov, M.V.: On the probability of being synchronizable. In: Govindarajan, S., Maheshwari, A. (eds.) Algorithms and Discrete Applied Mathematics. 2nd International Conference, CALDAM 2016. LNCS, vol. 9602, pp. 73–84. Springer (2016)
5.
Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. Cambridge University Press (2009)
6.
Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook on Satisfiability. IOS Press (2009)
7.
Bonizzoni, P., Jonoska, N.: Existence of constants in regular splicing languages. Inf. Comput. 242, 340–353 (2015)MathSciNetCrossRef
8.
Cerny, J.: Poznámka k homogénnym eksperimentom s konečnými automatami. Matematicko-fyzikalny Časopis Slovenskej Akadémie Vied 14(3), 208–216 (1964) (in Slovak); Engl. translation: A note on homogeneous experiments with finite automata. J. Autom. Lang. Comb. 24(2-4), 121–130 (2019)
9.
de Bondt, M., Don, H., Zantema, H.: Lower bounds for synchronizing word lengths in partial automata. Int. J. Found. Comput. Sci. 30(1), 29–60 (2019)MathSciNetCrossRef
10.
Don, H., Zantema, H.: Synchronizing non-deterministic finite automata. J. Autom. Lang. Comb. 23(4), 307–328 (2018)MathSciNetMATH
11.
Eén, N., Sörensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.), Theory and Applications of Satisfiability Testing. 6th International Conference, SAT 2003. LNCS, 2919, 502–518. Springer (2004)
12.
13.
14.
Gomes, C..P., Kautz, H., Sabharwal, A., Selman, B.: Satisfiability solvers. In: van Harmelen, F., Lifschitz, V., Porter, B. (eds.) Handbook of Knowledge Representation, vol. I, pp. 89–134. Elsevier (2008)
15.
Güniçen, C., Erdem, E., Yenigün, H.: Generating shortest synchronizing sequences using Answer Set Programming. In: Fink, M., Lierler, Yu. (eds.) Answer Set Programming and Other Computing Paradigms, 6th International Workshop, ASPOCP 2013, 117–127. https://​arxiv.​org/​abs/​1312.​6146 (2013)
16.
17.
Ito, M.: Algebraic Theory of Automata and Languages. World Scientific (2004)
18.
Kari, J., Volkov, M.V.: Černý’s conjecture and the road colouring problem. Chapter 15 in: J.-É. Pin (ed.), Handbook of Automata Theory, I, 525–565. EMS Press (2021)
19.
Kisielewicz, A., Kowalski, J., Szykuła, M.: Computing the shortest reset words of synchronizing automata. J. Comb. Optim. 29(1), 88–124 (2015)MathSciNetCrossRef
20.
Martyugin, P.V.: Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata. Diskretn. Anal. Issled. Oper. 15(4), 44–56 (2008) (in Russian)
21.
Martyugin, P.V.: A lower bound for the length of the shortest carefully synchronizing words. Russian Math. (Iz. VUZ) 54(1), 46–54 (2010)MathSciNetCrossRef
22.
Martyugin, P.V.: Synchronization of automata with one undefined or ambiguous transition. In: Moreira, N., Reis, R. (eds.), Implementation and Application of Automata, 17th International Conference, CIAA 2012. LNCS, 7381, 278–288. Springer (2012)
23.
Martyugin, P.V.: Careful synchronization of partial automata with restricted alphabets. In: Bulatov, A.A., Shur, A.M. (eds.) Computer Science—Theory and Applications, 8th International Computer Science Symposium in Russia, CSR 2013. LNCS, 7913, 76–87. Springer (2013)
24.
Martyugin, P.V.: Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA. Theory Comput. Syst. 54(2), 293–304 (2014)MathSciNetCrossRef
25.
Natarajan, B.K.: An algorithmic approach to the automated design of parts orienters. In: Proceedings of 27th Annual Symposium Foundations Computer Science, 132–142. IEEE Press (1986)
26.
Natarajan, B.K.: Some paradigms for the automated design of parts feeders. Int. J. Robotics Res. 8(6), 89–109 (1989)CrossRef
27.
Nicaud, C.: Fast synchronization of random automata. In: Jansen, K., Mathieu, C., Rolim, J.D.P., Umans, C. (eds), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX/RANDOM 2016. LIPIcs, 60, 43:1–43:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)
28.
Nicaud, C.: The Černý Conjecture holds with high probability. J. Autom. Lang. Comb. 24(2–4), 343–365 (2019)MathSciNetMATH
29.
Ramírez Alfonsín, J.L.: The Diophantine Frobenius Problem. Oxford University Press (2005)
30.
Rystsov, I.K.: Asymptotic estimate of the length of a diagnostic word for a finite automaton. Cybernetics 16(1), 194–198 (1980)MathSciNetCrossRef
31.
32.
Sandberg, S.: Homing and synchronizing sequences. In: Broy, M., Jonsson, B., Katoen, J.-P., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive Systems, LNCS, 3472, 5–33. Springer (2005)
33.
34.
Shabana, H.: Exact synchronization in partial deterministic automata. J. Phys. Conf. Ser. 1352, 1–8 (2019)CrossRef
35.
Shabana, H., Volkov, M.V.: Using Sat solvers for synchronization issues in nondeterministic automata. Siberian Electron. Math. Rep. 15, 1426–1442 (2018)MATH
36.
Shabana, H., Volkov, M.V.: Using Sat solvers for synchronization issues in partial deterministic automata. In: Bykadorov, I., Strsuevich, V.A., Tchemisova, T. (eds.), Mathematical Optimization Theory and Operation Research, 18th International Conference, MOTOR 2019. Communications in Computer and Information Science, Springer 1090, 103–118 (2019)
37.
Skvortsov, E., Tipikin, E.: Experimental study of the shortest reset word of random automata. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, J.-M., Maurel, D. (eds.), Implementation and Application of Automata, 16th International Conference, CIAA 2011. LNCS, Springer 6807, 290–298 (2011)
38.
Travers, N., Crutchfield, J.: Exact synchronization for finite-state sources. J. Stat. Phys. 145(5), 1181–1201 (2011)MathSciNetCrossRef
39.
Travers, N., Crutchfield, J.: Asymptotic synchronization for finite-state sources. J. Stat. Phys. 145(5), 1202–1223 (2011)MathSciNetCrossRef
40.
Türker, U.. C.: Parallel brute-force algorithm for deriving reset sequences from deterministic incomplete finite automata. Turk. J. Electr. Eng. Comput. Sci. 27, 3544–3556 (2019)CrossRef
41.
Volkov, M.V.: Synchronizing automata and the Černý conjecture. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.), Languages and Automata Theory and Applications, 2nd International Conference, LATA 2008. LNCS, Springer 5196, 11–27 (2008)
42.
Zubkov, A.M.: Computation of distributions of the numbers of components and cyclic points for random mappings. Mat. Vopr. Kriptogr., 1(2), 5–18 (2010) (in Russian)
Metadata
Title
Careful synchronization of partial deterministic finite automata
Authors
Hanan Shabana
M. V. Volkov
Publication date
22-07-2022
Publisher
Springer Berlin Heidelberg
Published in
Acta Informatica / Issue 4/2022
Print ISSN: 0001-5903
Electronic ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-022-00433-1

Other articles of this Issue 4/2022

Acta Informatica 4/2022 Go to the issue

Original Article

Depth-first search in directed planar graphs, revisited

Original Article

Lamplighter groups and automata

Original Article

Reoptimization of parameterized problems

Editorial

Preface to Klaus-Jörn Lange Festschrift

Original Article

Exploration of k-edge-deficient temporal graphs

Original Article

-reduction computation revisited

Premium Partner

    Image Credits