The Complexity of Revision

Authors
G. Aldo Antonelli
University of California, Davis
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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1305/ndjfl/1040609294
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 35,865
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Revision Without Revision Sequences: Self-Referential Truth.Edoardo Rivello - forthcoming - Journal of Philosophical Logic:1-29.
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.
Property Theory and the Revision Theory of Definitions.Francesco Orilia - 2000 - Journal of Symbolic Logic 65 (1):212-246.

View all 7 citations / Add more citations

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.G. 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.
A Paraconsistent Theory of Belief Revision.Edwin D. Mares - 2002 - Erkenntnis 56 (2):229 - 246.
Iterated Revision and Minimal Change of Conditional Beliefs.Craig Boutilier - 1996 - Journal of Philosophical Logic 25 (3):263 - 305.

Analytics

Added to PP index
2010-08-24

Total downloads
22 ( #285,044 of 2,293,801 )

Recent downloads (6 months)
1 ( #410,358 of 2,293,801 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature