Nonmonotonic reasoning is sometimes simpler

Grigori Schwarz; Mirostaw Truszczyński

doi:10.1007/bfb0022579

Nonmonotonic reasoning is sometimes simpler

Grigori Schwarz, Mirostaw Truszczyński

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Scopus citations

Abstract

We establish the complexity of decision problems associated with the nonmonotonic modal logic S4. We prove that the problem of existence of an S4-expansion for a given set A of premises is Σ₂ ^P-complete. Similarly, we show that for a given formula ϕ and a set A of premises, it is Σ₂ ^P-complete to decide whether ϕ belongs to at least one S4-expansion for A, and it is Π₂ ^P-complete to decide whether ϕ belongs to all S4-expansions for A. An interesting aspect of these results is that reasoning (testing satisfiability and provability) in the monotonic modal logic S4 is PSPACE-complete. To the best of our knowledge, the nonmonotonic logic S4 is the first example of a nonmonotoific formalism which is computationally easier than the monotonic logic that underlies it (assuming PSPACE does not collapse to Σ² _P).

Original language	English
Title of host publication	Computational Logic and Proof Theory - 3rd Kurt Godel Colloquium, KGC 1993, Proceedings
Editors	Georg Gottlob, Alexander Leitsch, Daniele Mundici
Pages	313-324
Number of pages	12
DOIs	https://doi.org/10.1007/bfb0022579
State	Published - 1993
Event	3rd Kurt Godel Colloquium on Computational Logic and Proof Theory, KGC 1993 - Brno, Czech Republic Duration: Aug 24 1993 → Aug 27 1993

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	713 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd Kurt Godel Colloquium on Computational Logic and Proof Theory, KGC 1993
Country/Territory	Czech Republic
City	Brno
Period	8/24/93 → 8/27/93

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0022579

Cite this

Schwarz, G., & Truszczyński, M. (1993). Nonmonotonic reasoning is sometimes simpler. In G. Gottlob, A. Leitsch, & D. Mundici (Eds.), Computational Logic and Proof Theory - 3rd Kurt Godel Colloquium, KGC 1993, Proceedings (pp. 313-324). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 713 LNCS). https://doi.org/10.1007/bfb0022579

Schwarz, Grigori ; Truszczyński, Mirostaw. / Nonmonotonic reasoning is sometimes simpler. Computational Logic and Proof Theory - 3rd Kurt Godel Colloquium, KGC 1993, Proceedings. editor / Georg Gottlob ; Alexander Leitsch ; Daniele Mundici. 1993. pp. 313-324 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{01a779f2c2b947e8a7db6e8ee43bb918,

title = "Nonmonotonic reasoning is sometimes simpler",

abstract = "We establish the complexity of decision problems associated with the nonmonotonic modal logic S4. We prove that the problem of existence of an S4-expansion for a given set A of premises is Σ2 P-complete. Similarly, we show that for a given formula ϕ and a set A of premises, it is Σ2 P-complete to decide whether ϕ belongs to at least one S4-expansion for A, and it is Π2 P-complete to decide whether ϕ belongs to all S4-expansions for A. An interesting aspect of these results is that reasoning (testing satisfiability and provability) in the monotonic modal logic S4 is PSPACE-complete. To the best of our knowledge, the nonmonotonic logic S4 is the first example of a nonmonotoific formalism which is computationally easier than the monotonic logic that underlies it (assuming PSPACE does not collapse to Σ2 P).",

author = "Grigori Schwarz and Mirostaw Truszczy{\'n}ski",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 3rd Kurt Godel Colloquium on Computational Logic and Proof Theory, KGC 1993 ; Conference date: 24-08-1993 Through 27-08-1993",

year = "1993",

doi = "10.1007/bfb0022579",

language = "English",

isbn = "9783540571841",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "313--324",

editor = "Georg Gottlob and Alexander Leitsch and Daniele Mundici",

booktitle = "Computational Logic and Proof Theory - 3rd Kurt Godel Colloquium, KGC 1993, Proceedings",

}

Schwarz, G & Truszczyński, M 1993, Nonmonotonic reasoning is sometimes simpler. in G Gottlob, A Leitsch & D Mundici (eds), Computational Logic and Proof Theory - 3rd Kurt Godel Colloquium, KGC 1993, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 713 LNCS, pp. 313-324, 3rd Kurt Godel Colloquium on Computational Logic and Proof Theory, KGC 1993, Brno, Czech Republic, 8/24/93. https://doi.org/10.1007/bfb0022579

Nonmonotonic reasoning is sometimes simpler. / Schwarz, Grigori; Truszczyński, Mirostaw.
Computational Logic and Proof Theory - 3rd Kurt Godel Colloquium, KGC 1993, Proceedings. ed. / Georg Gottlob; Alexander Leitsch; Daniele Mundici. 1993. p. 313-324 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 713 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Nonmonotonic reasoning is sometimes simpler

AU - Schwarz, Grigori

AU - Truszczyński, Mirostaw

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1993.

PY - 1993

Y1 - 1993

N2 - We establish the complexity of decision problems associated with the nonmonotonic modal logic S4. We prove that the problem of existence of an S4-expansion for a given set A of premises is Σ2 P-complete. Similarly, we show that for a given formula ϕ and a set A of premises, it is Σ2 P-complete to decide whether ϕ belongs to at least one S4-expansion for A, and it is Π2 P-complete to decide whether ϕ belongs to all S4-expansions for A. An interesting aspect of these results is that reasoning (testing satisfiability and provability) in the monotonic modal logic S4 is PSPACE-complete. To the best of our knowledge, the nonmonotonic logic S4 is the first example of a nonmonotoific formalism which is computationally easier than the monotonic logic that underlies it (assuming PSPACE does not collapse to Σ2 P).

AB - We establish the complexity of decision problems associated with the nonmonotonic modal logic S4. We prove that the problem of existence of an S4-expansion for a given set A of premises is Σ2 P-complete. Similarly, we show that for a given formula ϕ and a set A of premises, it is Σ2 P-complete to decide whether ϕ belongs to at least one S4-expansion for A, and it is Π2 P-complete to decide whether ϕ belongs to all S4-expansions for A. An interesting aspect of these results is that reasoning (testing satisfiability and provability) in the monotonic modal logic S4 is PSPACE-complete. To the best of our knowledge, the nonmonotonic logic S4 is the first example of a nonmonotoific formalism which is computationally easier than the monotonic logic that underlies it (assuming PSPACE does not collapse to Σ2 P).

UR - http://www.scopus.com/inward/record.url?scp=84936094091&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84936094091&partnerID=8YFLogxK

U2 - 10.1007/bfb0022579

DO - 10.1007/bfb0022579

M3 - Conference contribution

AN - SCOPUS:84936094091

SN - 9783540571841

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 313

EP - 324

BT - Computational Logic and Proof Theory - 3rd Kurt Godel Colloquium, KGC 1993, Proceedings

A2 - Gottlob, Georg

A2 - Leitsch, Alexander

A2 - Mundici, Daniele

T2 - 3rd Kurt Godel Colloquium on Computational Logic and Proof Theory, KGC 1993

Y2 - 24 August 1993 through 27 August 1993

ER -

Schwarz G, Truszczyński M. Nonmonotonic reasoning is sometimes simpler. In Gottlob G, Leitsch A, Mundici D, editors, Computational Logic and Proof Theory - 3rd Kurt Godel Colloquium, KGC 1993, Proceedings. 1993. p. 313-324. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0022579

Nonmonotonic reasoning is sometimes simpler

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this