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:
Buchtitelbild

2018 | OriginalPaper | Buchkapitel

The Completeness Problem for Modal Logic

verfasst von : Antonis Achilleos

Erschienen in: Logical Foundations of Computer Science

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We introduce the completeness problem for Modal Logic and examine its complexity. For a definition of completeness for formulas, given a formula of a modal logic, the completeness problem asks whether the formula is complete for that logic. We discover that completeness and validity have the same complexity — with certain exceptions for which there are, in general, no complete formulas. To prove upper bounds, we present a non-deterministic polynomial-time procedure with an oracle from PSPACE that combines tableaux and a test for bisimulation, and determines whether a formula is complete.

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
Nächstes Kapitel Justification Awareness Models
Fußnoten
1
According to our definition, for a finite model \(\mathcal {M}=(W,R,V)\) and \(a \in W\), V(a) can be infinite. However, we are mainly interested in \((W,R,V_P)\) for finite sets of propositions P, which justifies calling \(\mathcal {M}\) finite.
 
2
Although for the purposes of this paper we only consider a specific set of modal logics, it is interesting to note that the corollary can be extended to a much larger class of logics.
 
3
This is also a corollary of Lemma 4, as these are extensions of D and T.
 
4
We note that US is different from UP; for UP, if T has an accepting path for x, then it is guaranteed that it has a unique accepting path for x.
 
Literatur
1.
Ladner, R.E.: The computational complexity of provability in systems of modal propositional logic. SIAM J. Comput. 6(3), 467–480 (1977)MathSciNetCrossRefMATH
2.
Halpern, J.Y., Rêgo, L.C.: Characterizing the NP-PSPACE gap in the satisfiability problem for modal logic. J. Logic Comput. 17(4), 795–806 (2007)MathSciNetCrossRefMATH
3.
Halpern, J.Y., Moses, Y.: A guide to completeness and complexity for modal logics of knowledge and belief. Artif. Intell. 54(3), 319–379 (1992)MathSciNetCrossRefMATH
4.
Artemov, S.: Syntactic epistemic logic. In: Book of Abstracts, 15th Congress of Logic, Methodology and Philosophy of Science CLMPS 2015, pp. 109–110 (2015)
5.
Artemov, S.: Syntactic epistemic logic and games (2016)
6.
Hennessy, M., Milner, R.: Algebraic laws for nondeterminism and concurrency. J. ACM (JACM) 32(1), 137–161 (1985)CrossRefMATH
7.
Milner, R.: Communication and Concurrency. Prentice-Hall Inc., Upper Saddle River (1989)MATH
8.
Graf, S., Sifakis, J.: A modal characterization of observational congruence on finite terms of CCS. Inf. Control 68(1–3), 125–145 (1986)MathSciNetCrossRefMATH
9.
Steffen, B., Ingólfsdóttir, A.: Characteristic formulas for processes with divergence. Inf. Comput. 110(1), 149–163 (1994)CrossRefMATH
10.
11.
12.
13.
Achilleos, A.: The completeness problem for modal logic. CoRR abs/1605.01004 (2016)
14.
Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge (2001)CrossRefMATH
15.
Chagrov, A., Zakharyaschev, M.: Modal Logic. Oxford University Press, Oxford (1997)MATH
16.
17.
18.
19.
20.
21.
Metadaten
Titel
The Completeness Problem for Modal Logic
verfasst von
Antonis Achilleos
Copyright-Jahr
2018
Buch
Logical Foundations of Computer Science

Print ISBN: 978-3-319-72055-5

Electronic ISBN: 978-3-319-72056-2

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-72056-2_1

Premium Partner

    Bildnachweise