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:
Skolemization for Substructural Logics Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

On CTL* with Graded Path Modalities

verfasst von : Benjamin Aminof, Aniello Murano, Sasha Rubin

Erschienen in: Logic for Programming, Artificial Intelligence, and Reasoning

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

Graded path modalities count the number of paths satisfying a property, and generalize the existential (\(\mathsf {E}\)) and universal \((\mathsf {A})\) path modalities of \(\textsc {CTL}^{*}\). The resulting logic is denoted \(\textsc {G}\textsc {CTL}^{*}\), and is a very powerful logic since (as we show) it is equivalent, over trees, to monadic path logic. We settle the complexity of the satisfiability problem of \(\textsc {G}\textsc {CTL}^{*}\), i.e., 2ExpTime-Complete, and the complexity of the model checking problem of \(\textsc {G}\textsc {CTL}^{*}\), i.e., PSpace-Complete. The lower bounds already hold for \(\textsc {CTL}^{*}\), and so we supply the upper bounds. The significance of this work is two-fold: \(\textsc {G}\textsc {CTL}^{*}\) is much more expressive than \(\textsc {CTL}^{*}\) as it adds to it a form of quantitative reasoning, and this is done at no extra cost in computational complexity.

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 Focused Labeled Proof Systems for Modal Logic
Nächstes Kapitel On Subexponentials, Synthetic Connectives, and Multi-level Delimited Control
Fußnoten
1
Strictly speaking, GHTA generalise the symmetric variant of AHTA. That is, for every language accepted by an AHTA and that is closed under the operation of permuting siblings, there is a GHTA that accepts the same language.
 
2
The combination of a Büchi and a co-Büchi condition that hesitant automata use can be thought of as a special case of the parity condition with 3 colors. Thus, we could have defined Graded Parity Tree Automata instead (using the parity condition, our automata strictly generalise the ones in [5, 19]) However, we do not need the full power of the parity condition, and in order to achieve optimal complexity for model checking of \(\textsc {G}\textsc {CTL}^{*}\) we need to be able to decide membership of our automata in a space efficient way, which cannot be done with the parity acceptance condition.
 
3
For example, when building an automaton for \(\phi = \varphi _0 \vee \varphi _1\), in the degenerate case that \(\varphi _0 = \varphi _1\) then \(\mathsf {A}_{\varphi _1}\) is taken to be a copy of \(\mathsf {A}_{\varphi _0}\) with its states renamed to be disjoint from those of \(\mathsf {A}_{\varphi _0}\). Also, the new state \(q_0\) may be renamed to avoid a collision with any of the other states.
 
Literatur
1.
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
2.
Aminof, B., Kupferman, O., Lampert, R.: Rigorous approximated determinization of weighted automata. In: Symposium on Logic in Computer Science, pp. 345–354, IEEE (2011)
3.
4.
Arenas, M., Barceló, P., Libkin, L.: Combining temporal logics for querying XML documents. In: Schwentick, T., Suciu, D. (eds.) ICDT 2007. LNCS, vol. 4353, pp. 359–373. Springer, Heidelberg (2006) CrossRef
5.
Bianco, A., Mogavero, F., Murano, A.: Graded computation tree logic. In: Symposium on Logic in Computer Science, pp. 342–351, IEEE (2009)
6.
Bianco, A., Mogavero, F., Murano, A.: Graded computation tree logic. ACM Trans. Comput. Log. 13(3), 25 (2012)MathSciNetCrossRef
7.
Bonatti, P.A., Lutz, C., Murano, A., Vardi, M.Y.: The complexity of enriched Mu-Calculi. Log. Methods Comput. Sci. 4(3), 1–27 (2008)MathSciNetCrossRef
8.
Calvanese, D., De Giacomo, G., Lenzerini, M.: Reasoning in expressive description logics with fixpoints based on automata on infinite trees. In: International Joint Conference on Artificial Intelligence, pp. 84–89 (1999)
9.
10.
Droste, M., Kuich, W., Vogler, H.: Handbook of Weighted Automata. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2009) MATHCrossRef
11.
Eisner, C., Fisman, D., Havlicek, J., Lustig, Y., McIsaac, A., Van Campenhout, D.: Reasoning with temporal logic on truncated paths. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol. 2725, pp. 27–39. Springer, Heidelberg (2003) CrossRef
12.
13.
Emerson, E.A., Sistla, A.P.: Deciding branching time logic, pp. 14–24. In: Symposium on Theory of Computing (1984)
14.
Ferrante, A., Murano, A., Parente, M.: Enriched \(\mu \)-calculi module checking. Log. Methods Comput. Sci. 4(3), 1–21 (2008)
15.
Ferrante, A., Napoli, M., Parente, M.: Model checking for graded CTL. Fundamenta Informaticae 96(3), 323–339 (2009)MATHMathSciNet
16.
17.
Gutiérrez-Basulto, V., Jung, J.C., Lutz, C.: Complexity of branching temporal description logics. In: European Conference on Artificial Intelligence, pp. 390–395 (2012)
18.
Henzinger, T.A.: Quantitative reactive modeling and verification. Comput. Sci. 28(4), 331–344 (2013)
19.
Kupferman, O., Sattler, U., Vardi, M.Y.: The complexity of the graded \(\mu \)-calculus. In: Voronkov, A. (ed.) CADE 2002. LNCS (LNAI), vol. 2392, pp. 423–437. Springer, Heidelberg (2002) CrossRef
20.
Kupferman, O., Vardi, M.Y., Wolper, P.: An automata theoretic approach to branching-time model checking. J. ACM 47(2), 312–360 (2000)MATHMathSciNetCrossRef
21.
Malvone, V., Mogavero, F., Murano, A., Sorrentino, L.: On the counting of strategies. In: International Symposium on Temporal Representation and Reasoning, IEEE (2015, to appear)
22.
Moller, F., Rabinovich, A.: Counting on CTL*: on the expressive power of monadic path logic. Inf. Comput. 184(1), 147–159 (2003)MATHMathSciNetCrossRef
23.
24.
van der Hoek, W., Meyer, JJ.Ch.: Graded modalities in epistemic logic. In: Symposium on Logical Foundations of Computer Science, pp. 503–514 (1992)
25.
Metadaten
Titel
On CTL* with Graded Path Modalities
verfasst von
Benjamin Aminof
Aniello Murano
Sasha Rubin
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Logic for Programming, Artificial Intelligence, and Reasoning

Print ISBN: 978-3-662-48898-0

Electronic ISBN: 978-3-662-48899-7

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-48899-7_20