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:
Minimal and Monotone Minimal Perfect Hash Functions Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Weighted Automata and Logics on Graphs

verfasst von : Manfred Droste, Stefan Dück

Erschienen in: Mathematical Foundations of Computer Science 2015

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

Weighted automata model quantitative features of the behavior of systems and have been investigated for various structures like words, trees, traces, pictures, and nested words. In this paper, we introduce a general model of weighted automata acting on graphs, which form a quantitative version of Thomas’ unweighted model of graph acceptors. We derive a Nivat theorem for weighted graph automata which shows that their behaviors are precisely those obtainable from very particular weighted graph automata and unweighted graph acceptors with a few simple operations. We also show that a suitable weighted MSO logic is expressively equivalent to weighted graph automata. As a consequence, we obtain corresponding Büchi-type equivalence results known from the recent literature for weighted automata and weighted logics on words, trees, pictures, and nested words. Establishing such a general result has been an open problem for weighted logic for some time.

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 Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus
Nächstes Kapitel Longest Gapped Repeats and Palindromes
Literatur
1.
2.
Anselmo, M., Giammarresi, D., Madonia, M., Restivo, A.: Unambiguous recognizable two-dimensional languages. ITA 40(2), 277–293 (2006)MathSciNetMATH
3.
Berstel, J., Reutenauer, C.: Rational Series and Their Languages. EATCS Monographs in Theoretical Computer Science, vol. 12. Springer, Heidelberg (1988)CrossRefMATH
4.
Bollig, B., Gastin, P.: Weighted versus probabilistic logics. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 18–38. Springer, Heidelberg (2009) CrossRef
5.
Bollig, B., Gastin, P., Monmege, B., Zeitoun, M.: Pebble weighted automata and weighted logics. ACM Trans. Comput. Log. 15(2), 15 (2014)MathSciNetCrossRef
6.
Büchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundlagen Math. 6, 66–92 (1960)CrossRefMATH
7.
8.
Droste, M., Dück, S.: Weighted automata and logics for infinite nested words. In: Dediu, A.-H., Martín-Vide, C., Sierra-Rodríguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 323–334. Springer, Heidelberg (2014) CrossRef
9.
10.
Droste, M., Gastin, P.: Weighted automata and weighted logics. In: Droste et al. [11], chapter 5, pp. 175–211
11.
Droste, M., Kuich, W., Vogler, H. (eds.): Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science. Springer, Heidelberg (2009)
12.
Droste, M., Kuske, D.: Weighted automata. In: Pin, J.E. (ed.) Handbook: “Automata: from Mathematics to Applications". Europ. Mathematical Soc. (to appear)
13.
Droste, M., Perevoshchikov, V.: A Nivat theorem for weighted timed automata and weighted relative distance logic. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 171–182. Springer, Heidelberg (2014)
14.
15.
Eilenberg, S.: Automata, Languages, and Machines, Pure and Applied Mathematics, vol. 59-A. Academic Press, New York (1974)
16.
Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc. 98(1), 21–52 (1961)MathSciNetCrossRef
17.
18.
Giammarresi, D., Restivo, A., Seibert, S., Thomas, W.: Monadic second-order logic over rectangular pictures and recognizability by tiling systems. Inf. Comput. 125(1), 32–45 (1996)MathSciNetCrossRefMATH
19.
Golan, J.S.: Semirings and their Applications. Kluwer Academic Publishers, Dordrecht (1999) CrossRefMATH
20.
Hanf, W.: Model-theoretic methods in the study of elementary logic. In: Addison, J., Henkin, L., Tarski, A. (eds.) The Theory of Models, pp. 132–145. Amsterdam, North-Holland (1965)
21.
22.
Kuich, W., Salomaa, A.: Semirings, Automata, Languages. EATCS Monographs in Theoretical Computer Science, vol. 6. Springer, Heidelberg (1986)
23.
24.
Mathissen, C.: Weighted logics for nested words and algebraic formal power series. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 221–232. Springer, Heidelberg (2008) CrossRef
25.
Meinecke, I.: Weighted logics for traces. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol. 3967, pp. 235–246. Springer, Heidelberg (2006) CrossRef
26.
Monmege, B.: Specification and Verification of Quantitative Properties: Expressions, Logics, and Automata. Thèse de doctorat, ENS Cachan, France (2013)
27.
28.
Rabin, M.O.: Decidability of second order theories and automata on infinite trees. Trans. Am. Math. Soc. 141, 1–35 (1969)MathSciNetMATH
29.
Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs in Computer Science. Springer, New York (1978) CrossRef
30.
Schützenberger, M.P.: On the definition of a family of automata. Inf. Control 4(2–3), 245–270 (1961)CrossRefMATH
31.
Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory 2(1), 57–81 (1968)MathSciNetCrossRef
32.
Thomas, W.: On logical definability of trace languages. In: Diekert, V. (ed.) Proceedings of workshop ASMICS 1989, pp. 172–182. Technical University of Munich (1990)
33.
Thomas, W.: On logics, tilings, and automata. In: Leach Albert, J., Monien, B., Rodríguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol. 510, pp. 441–454. Springer, Heidelberg (1991) CrossRef
34.
Thomas, W.: Elements of an automata theory over partial orders. In: Proceedings of DIMACS Workshop POMIV 1996, pp. 25–40. AMS Press Inc, New York, USA (1996)
35.
Trakhtenbrot, B.A.: Finite automata and logic of monadic predicates (in Russian). Doklady Akademii Nauk SSR 140, 326–329 (1961)
Metadaten
Titel
Weighted Automata and Logics on Graphs
verfasst von
Manfred Droste
Stefan Dück
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Mathematical Foundations of Computer Science 2015

Print ISBN: 978-3-662-48056-4

Electronic ISBN: 978-3-662-48057-1

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-48057-1_15