The Complexity of Revision

Notre Dame Journal of Formal Logic 35 (1):67-72 (1994)
  Copy   BIBTEX

Abstract

In this paper we show that the Gupta-Belnap systems S# and S* are П12. Since Kremer has independently established that they are П12-hard, this completely settles the problem of their complexity. The above-mentioned upper bound is established through a reduction to countable revision sequences that is inspired by, and makes use of a construction of McGee.

Categories

Keywords

Reprint years

DOI

10.1305/ndjfl/1040609294

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,752

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The Complexity of Revision, revised.Aldo Antonelli - 2002 - Notre Dame Journal of Formal Logic 43 (2):75-78.
Non-well-founded sets via revision rules.Gian Aldo Antonelli - 1994 - Journal of Philosophical Logic 23 (6):633 - 679.
What's in a function?Gian Aldo Antonelli - 1996 - Synthese 107 (2):167 - 204.
A Revision-Theoretic Analysis of the Arithmetical Hierarchy.Gian Aldo Antonelli - 1994 - Notre Dame Journal of Formal Logic 35 (2):204-218.
Selective revision.Eduardo L. Fermé & Sven Ove Hansson - 1999 - Studia Logica 63 (3):331-342.
Complexity and sustainability.Jennifer Wells - 2013 - New York: Routledge.
Revision Rules: An Investigation into Non-Monotonic Inductive Definitions.G. Aldo Antonelli - 1992 - Dissertation, University of Pittsburgh
On Gupta-Belnap revision theories of truth, Kripkean fixed points, and the next stable set.P. D. Welch - 2001 - Bulletin of Symbolic Logic 7 (3):345-360.
Controlled revision - an algorithmic approach for belief revision.Gabriella Pigozzi - manuscript
Credibility limited revision.Sven Ove Hansson, Eduardo Leopoldo Fermé, John Cantwell & Marcelo Alejandro Falappa - 2001 - Journal of Symbolic Logic 66 (4):1581-1596.
A paraconsistent theory of belief revision.Edwin D. Mares - 2002 - Erkenntnis 56 (2):229 - 246.
Complexity theory, systems theory, and multiple intersecting social inequalities.Sylvia Walby - 2007 - Philosophy of the Social Sciences 37 (4):449-470.
Iterated revision and minimal change of conditional beliefs.Craig Boutilier - 1996 - Journal of Philosophical Logic 25 (3):263 - 305.
Bounded Revision: Two-Dimensional Belief Change Between Conservative and Moderate Revision.Hans Rott - 2012 - Journal of Philosophical Logic 41 (1):173-200.
Synthetic analysis: How science combats complexity.Sunny Auyang - manuscript

Analytics

Added to PP
2010-08-24

Downloads
43 (#368,455)

6 months
14 (#176,812)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

G. Aldo Antonelli
University of California, Davis

Citations of this work

Conditionals in Theories of Truth.Anil Gupta & Shawn Standefer - 2017 - Journal of Philosophical Logic 46 (1):27-63.
Solovay-type theorems for circular definitions.Shawn Standefer - 2015 - Review of Symbolic Logic 8 (3):467-487.
Guest Editors’ Introduction.Riccardo Bruni & Shawn Standefer - 2019 - Journal of Philosophical Logic 48 (1):1-9.
Revision Without Revision Sequences: Self-Referential Truth.Edoardo Rivello - 2019 - Journal of Philosophical Logic 48 (3):523-551.
Property theory and the revision theory of definitions.Francesco Orilia - 2000 - Journal of Symbolic Logic 65 (1):212-246.

View all 12 citations / Add more citations

References found in this work

The Gupta-Belnap systems ${\rm S}^\#$ and ${\rm S}^*$ are not axiomatisable.Philip Kremer - 1993 - Notre Dame Journal of Formal Logic 34 (4):583-596.
The Guptα-Belnαp Systems S and S* are not Axiomatisable.Philip Kremer - 1993 - Notre Dame Journal of Formal Logic 34 (4):583-596.

Add more references