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:
Computers and the Mechanics of Communication Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Weighted Automata on Infinite Words in the Context of Attacker-Defender Games

verfasst von : Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov

Erschienen in: Evolving Computability

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We consider several infinite-state Attacker-Defender games with reachability objectives. The results of the paper are twofold. Firstly we prove a new language-theoretic result for weighted automata on infinite words and show its encoding into the framework of Attacker-Defender games. Secondly we use this novel concept to prove undecidability for checking existence of a winning strategy in several low-dimensional mathematical games including vector reachability games, word games and braid games.

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 Randomness and Differentiability of Convex Functions
Nächstes Kapitel Turing Jumps Through Provability
Literatur
1.
Abdulla, P.A., Bouajjani, A., d’Orso, J.: Deciding monotonic games. In: Baaz, M., Makowsky, J.A. (eds.) CSL 2003. LNCS, vol. 2803, pp. 1–14. Springer, Heidelberg (2003) CrossRef
2.
Almagor, S., Boker, U., Kupferman, O.: What’s decidable about weighted automata? In: Bultan, T., Hsiung, P.-A. (eds.) ATVA 2011. LNCS, vol. 6996, pp. 482–491. Springer, Heidelberg (2011) CrossRef
3.
4.
Arul, A., Reichert, J.: The complexity of robot games on the integer line. In: Proceedings of QAPL 2013, EPTCS, vol. 117, pp. 132–148 (2013)
5.
Bell, P.C., Potapov, I.: On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups. Int. J. Found. Comput. Sci. 21(6), 963–978 (2010)MATHMathSciNetCrossRef
6.
Bell, P.C., Potapov, I.: On the computational complexity of matrix semigroup problems. Fundam. Inform. 116(1–4), 1–13 (2012)MATHMathSciNet
7.
Birget, J.C., Margolis, S.W.: Two-letter group codes that preserve aperiodicity of inverse finite automata. Semigroup Forum. 76, 159–168 (2008). SpringerMATHMathSciNetCrossRef
8.
9.
Brázdil, T., Jančar, P., Kučera, A.: Reachability games on extended vector addition systems with states. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 478–489. Springer, Heidelberg (2010) CrossRef
10.
Carlucci, L., Dehornoy, P., Weiermann, A.: Unprovability results involving braids. Proc. Lond. Math. Soc. 102(1), 159–192 (2011)MATHMathSciNetCrossRef
11.
Chatterjee, K., Fijalkow, N.: Infinite-state games with finitary conditions. In: Proceedings of CSL 2013, LIPIcs, vol. 23, pp. 181–196 (2013)
12.
Collins, G.P.: Computing with quantum knots. Sci. Am. 294(4), 56–63 (2006)CrossRef
13.
Dehornoy, P., Dynnikov, I., Rolfsen, D., Wiest, B.: Ordering Braids. Mathematical Surveys and Monographs, vol. 148. American Mathematical Society, Providence (2008) MATH
14.
Dong, J., Liu, Q.: Undecidability of infinite post correspondence problem for instances of size 8. RAIRO - Theor. Inf. Appl. 46(3), 451–457 (2012)MATHMathSciNetCrossRef
15.
Doyen, L., Rabinovich, A.: Robot games. Technical report LSV-13-02, LSV, ENS Cachan (2013)
16.
Epstein, D., Paterson, M., Cannon, J., Holt, D., Levy, S., Thurston, W.P.: Word Processing in Groups. AK Peters, Ltd, USA (1992)MATH
17.
Garber, D.: Braid group cryptography. In: Braids: Introductory Lectures on Braids, Configurations and Their Applications, vol. 19, pp. 329 (2010)
18.
Halava, V., Harju, T.: Undecidability in integer weighted finite automata. Fundam. Inform. 38(1–2), 189–200 (1999)MATHMathSciNet
19.
Halava, V., Harju, T.: Undecidability of infinite post correspondence problem for instances of size 9. ITA 40(4), 551–557 (2006)MATHMathSciNet
20.
Halava, V., Harju, T., Niskanen, R., Potapov, I.: Weighted automata on infinite words in the context of attacker-defender games (2015). CoRR. abs/​1411.​4796
21.
22.
23.
Kupferman, O., Vardi, M.Y., Wolper, P.: An automata-theoretic approach to branching-time model checking. J. ACM 47(2), 312–360 (2000)MATHMathSciNetCrossRef
24.
Ly, O., Wu, Z.: On effective construction of the greatest solution of language inequality XA \(\subseteq \) BX. Theor. Comput. Sci. 528, 12–31 (2014)MATHMathSciNetCrossRef
25.
Matiyasevich, Y., Sénizergues, G.: Decision problems for semi-thue systems with a few rules. Theor. Comput. Sci. 330(1), 145–169 (2005)MATHCrossRef
26.
Panangaden, P., Paquette, É.O.: A categorical presentation of quantum computation with anyons. In: Coecke, B. (ed.) New Structures for Physics. LNP, pp. 983–1025. Springer, Heidelberg (2011)
27.
28.
Potapov, I.: Composition problems for braids. In: Proceedings of FSTTCS 2003, LIPIcs, vol. 24, pp. 175–187 (2003)
29.
Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Bull. Am. Math. Soc. 74(5), 1025–1029 (1968)MATHMathSciNetCrossRef
30.
Ruohonen, K.: Reversible machines and post’s correspondence problem for biprefix morphisms. J. of Information Processing and Cybernetics 21(12), 579–595 (1985)MATHMathSciNet
31.
Metadaten
Titel
Weighted Automata on Infinite Words in the Context of Attacker-Defender Games
verfasst von
Vesa Halava
Tero Harju
Reino Niskanen
Igor Potapov
Copyright-Jahr
2015
Buch
Evolving Computability

Print ISBN: 978-3-319-20027-9

Electronic ISBN: 978-3-319-20028-6

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-20028-6_21