Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Acta Informatica
Erschienen in: Acta Informatica 4/2022

22.07.2022 | Original Article

Careful synchronization of partial deterministic finite automata

verfasst von: Hanan Shabana, M. V. Volkov

Erschienen in: Acta Informatica | Ausgabe 4/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel Lamplighter groups and automata
Nächster Artikel On the decidability of finding a positive ILP-instance in a regular set of ILP-instances

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
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’.
 
Literatur
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)
Metadaten
Titel
Careful synchronization of partial deterministic finite automata
verfasst von
Hanan Shabana
M. V. Volkov
Publikationsdatum
22.07.2022
Verlag
Springer Berlin Heidelberg
Erschienen in
Acta Informatica / Ausgabe 4/2022
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-022-00433-1

Weitere Artikel der Ausgabe 4/2022

Acta Informatica 4/2022 Zur Ausgabe

Original Article

On the decidability of finding a positive ILP-instance in a regular set of ILP-instances

Original Article

Reoptimization of parameterized problems

Editorial

Preface to Klaus-Jörn Lange Festschrift

Original Article

Properties of graphs specified by a regular language

Original Article

Operational complexity and pumping lemmas

Original Article

Lamplighter groups and automata

Premium Partner

    Bildnachweise