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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Minimization of Systemic Risk for Directed Network Using Genetic Algorithm Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

A New Evolutionary Algorithm for Synchronization

verfasst von : Jakub Kowalski, Adam Roman

Erschienen in: Applications of Evolutionary Computation

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

A synchronizing word brings all states of a finite automaton to the one particular state. From practical reasons the synchronizing words should be as short as possible. Unfortunately, the decision version of the problem is NP-complete. In this paper we present a new evolutionary approach for finding possibly short synchronizing words for a given automaton. As the optimization problem has two contradicting goals (the word’s length and the word’s rank) we use a 2 population feasible-infeasible approach. It is based on the knowledge on words’ ranks of all prefixes of a given word. This knowledge makes the genetic operators more efficient than in case of the standard letter-based operators.

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

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
Vorheriges Kapitel Presenting the ECO: Evolutionary Computation Ontology
Nächstes Kapitel Large Scale Problems in Practice: The Effect of Dimensionality on the Interaction Among Variables
Literatur
1.
Černý, J.: Poznámka k homogénnym eksperimentom s konečnými automatami. Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied 14(3), 208–216 (1964). In Slovak
2.
Pomeranz, I., Reddy, S.: On achieving complete testability of synchronous sequential circuits with synchronizing sequences. In: IEEE Proceedings of International Test Conference, pp. 1007–1016 (1994)
3.
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). doi:10.​1007/​11498490_​2CrossRef
4.
Benenson, Y., Adar, R., Paz-Elizur, T., Livneh, Z., Shapiro, E.: DNA molecule provides a computing machine with both data and fuel. Proc. Natl. Acad. Sci. 100(5), 2191–2196 (2003)CrossRef
5.
6.
7.
Berlinkov, M.V.: Approximating the minimum length of synchronizing words is hard. Theory Comput. Syst. 54(2), 211–223 (2014)MathSciNetCrossRefMATH
8.
9.
Roman, A.: Synchronizing finite automata with short reset words. In: Applied Mathematics and Computation. ICCMSE-2005, vol. 209, pp. 125–136 (2009)
10.
Roman, A., Szykuła, M.: Forward and backward synchronizing algorithms. Expert Syst. Appl. 42(24), 9512–9527 (2015)CrossRef
11.
Kisielewicz, A., Kowalski, J., Szykuła, M.: A fast algorithm finding the shortest reset words. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 182–196. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38768-5_​18CrossRef
12.
Kisielewicz, A., Kowalski, J., Szykuła, M.: Computing the shortest reset words of synchronizing automata. J. Comb. Optim. 29(1), 88–124 (2015)MathSciNetCrossRefMATH
13.
Trahtman, A.N.: An efficient algorithm finds noticeable trends and examples concerning the Černy conjecture. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 789–800. Springer, Heidelberg (2006). doi:10.​1007/​11821069_​68CrossRef
14.
15.
Kimbrough, S.O., Koehler, G.J., Lu, M., Wood, D.H.: On a feasible-infeasible two-population (FI-2Pop) genetic algorithm for constrained optimization: distance tracing and no free lunch. Eur. J. Oper. Res. 190(2), 310–327 (2008)MathSciNetCrossRefMATH
16.
Togelius, J., Yannakakis, G.N., Stanley, K.O., Browne, C.: Search-based procedural content generation: a taxonomy and survey. IEEE Trans. Comput. Intell. AI Games 3(3), 172–186 (2011)CrossRef
17.
Liapis, A., Yannakakis, G.N., Togelius, J.: Sentient sketchbook: computer-aided game level authoring. In: Conference on the Foundations of Digital Games, pp. 213–220 (2013)
18.
Liapis, A., Holmgård, C., Yannakakis, G.N., Togelius, J.: Procedural personas as critics for dungeon generation. In: Mora, A.M., Squillero, G. (eds.) EvoApplications 2015. LNCS, vol. 9028, pp. 331–343. Springer, Cham (2015). doi:10.​1007/​978-3-319-16549-3_​27
19.
Scirea, M., Togelius, J., Eklund, P., Risi, S.: MetaCompose: a compositional evolutionary music composer. In: Johnson, C., Ciesielski, V., Correia, J., Machado, P. (eds.) EvoMUSART 2016. LNCS, vol. 9596, pp. 202–217. Springer, Cham (2016). doi:10.​1007/​978-3-319-31008-4_​14CrossRef
20.
Ananichev, D.S., Volkov, M.V., Zaks, Y.I.: Synchronizing automata with a letter of deficiency 2. In: Ibarra, O.H., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 433–442. Springer, Heidelberg (2006). doi:10.​1007/​11779148_​39CrossRef
21.
22.
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)MathSciNetCrossRefMATH
23.
Metadaten
Titel
A New Evolutionary Algorithm for Synchronization
verfasst von
Jakub Kowalski
Adam Roman
Copyright-Jahr
2017
Buch
Applications of Evolutionary Computation

Print ISBN: 978-3-319-55848-6

Electronic ISBN: 978-3-319-55849-3

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-55849-3_40

Premium Partner

    Bildnachweise