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

Complexity of Propositional Independence and Inclusion Logic

verfasst von : Miika Hannula, Juha Kontinen, Jonni Virtema, Heribert Vollmer

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

We classify the computational complexity of the satisfiability, validity and model-checking problems for propositional independence and inclusion logic and their extensions by the classical negation.

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 Finitary Semantics of Linear Logic and Higher-Order Model-Checking
Nächstes Kapitel Modal Inclusion Logic: Being Lax is Simpler than Being Strict
Fußnoten
1
It is easy to show that all of the logics considered in this article have the so-called locality property, i.e., satisfaction of a formula depends only on the values of the proposition symbols that occur in the formula [5].
 
Literatur
1.
Buss, S.: The Boolean formula value problem is in ALOGTIME. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987, pp. 123–131, ACM, New York (1987)
2.
3.
Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC 1971, pp. 151–158. ACM, New York (1971)
4.
Ebbing, J., Lohmann, P.: Complexity of model checking for modal dependence logic. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Turán, G. (eds.) SOFSEM 2012. LNCS, vol. 7147, pp. 226–237. Springer, Heidelberg (2012) CrossRef
5.
Galliani, P.: Inclusion and exclusion dependencies in team semantics: on some logics of imperfect information. Ann. Pure Appl. Logic 163(1), 68–84 (2012)MathSciNetCrossRefMATH
6.
Grädel, E., Väänänen, J.: Dependence and independence. Stud. Logica 101(2), 399–410 (2013)CrossRefMATH
7.
Hannula, M., Kontinen, J.: A finite axiomatization of conditional independence and inclusion dependencies. In: Beierle, C., Meghini, C. (eds.) FoIKS 2014. LNCS, vol. 8367, pp. 211–229. Springer, Heidelberg (2014) CrossRef
8.
Hannula, M., Kontinen, J., Virtema, J., Vollmer, H.: Complexity of propositional independence and inclusion logic. In: CoRR, (2015). abs/​1504.​06135
9.
10.
Hella, L., Kuusisto, A., Meier, A., Vollmer, H.: Modal inclusion logic: Being lax is simpler than being strict. In: Italiano, G.F., et al. (eds.) MFCS 2015, Part I, LNCS, vol. 9234, pp. 281–292. Springer, Heidelberg (2015)
11.
Kontinen, J., Müller, J.-S., Schnoor, H., Vollmer, H.: A van Benthem theorem for modal team semantics. In: CoRR (2014). abs/​1410.​6648
12.
Kontinen, J., Nurmi, V.: Team logic and second-order logic. Fundam. Inform. 106(2–4), 259–272 (2011)MathSciNetMATH
13.
Levin, L.A.: Universal search problems. Probl. Inf. Transm. 9(3), 265–266 (1973)
14.
15.
Orponen, P.: Complexity classes of alternating machines with oracles. In: Diaz, J. (ed.) Automata, Languages and Programming. LNCS, vol. 154, pp. 573–584. Springer, Heidelberg (1983)CrossRef
16.
17.
18.
Virtema, J.: Complexity of validity for propositional dependence logics. In: Peron, A., Piazza, C. (eds.) Proceedings Fifth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2014, Verona, Italy. EPTCS, vol. 161, pp. 18–31, 10–12 September 2014
19.
Yang, F.: On extensions and variants of dependence logic. Ph.D. thesis, University of Helsinki (2014)
20.
Yang, F., Väänänen, J.: Propositional logics of dependence and independence. In: Part I. CoRR (2014). abs/​1412.​7998
Metadaten
Titel
Complexity of Propositional Independence and Inclusion Logic
verfasst von
Miika Hannula
Juha Kontinen
Jonni Virtema
Heribert Vollmer
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_21