The complexity of predicate default logic over a countable domain

Annals of Pure and Applied Logic 120 (1-3):151-163 (2003)
  Copy   BIBTEX

Abstract

Lifschitz introduced the notion of defining extensions of predicate default theories not as absolute, but relative to a specified domain. We look specifically at default theories over a countable domain and show the set of default theories which possess an ω -extension is Σ 2 1 -complete. That the set is in Σ 2 1 is shown by writing a nearly circumscriptive formula whose ω -models correspond to the ω -extensions of a given default theory; similarly, Σ 2 1 -hardness is established by a method for translating formulas into default theories in such a way that ω -models of the circumscriptive formula correspond to ω -extensions of the default theory

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(02)00064-7

Links

PhilArchive



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

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

Intermediate predicate logics determined by ordinals.Pierluigi Minari, Mitio Takano & Hiroakira Ono - 1990 - Journal of Symbolic Logic 55 (3):1099-1124.
Vagueness and domain restriction.Peter Pagin - unknown
Proof complexity of propositional default logic.Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas & Heribert Vollmer - 2011 - Archive for Mathematical Logic 50 (7-8):727-742.
Domains of Discourse.Philip Hugly & Charles Sayward - 1987 - Logique Et Analyse 117 (17):173-176.
Three complexity problems in quantified fuzzy logic.Franco Montagna - 2001 - Studia Logica 68 (1):143-152.
The Translation of First Order Logic into Modal Predicate Logic.Beomin Kim - 2008 - Proceedings of the Xxii World Congress of Philosophy 13:65-69.
An interpretation of default logic in minimal temporal epistemic logic.Joeri Engelfriet & Jan Treur - 1998 - Journal of Logic, Language and Information 7 (3):369-388.
Countable Fréchetα 1-spaces may be first countable.Alan Dow & Juris Stepräns - 1992 - Archive for Mathematical Logic 32 (1):33-50.
Logic: an introduction.Greg Restall - 2006 - New York: Routledge.
Countable model theory and large cardinals.Harvey Friedman - manuscript
Monadic fuzzy predicate logics.Petr Hájek - 2002 - Studia Logica 71 (2):165-175.
A note on countable models of 1-based theories.Predrag Tanovic - 2002 - Archive for Mathematical Logic 41 (7):669-671.
Isomorphism of Homogeneous Structures.John D. Clemens - 2009 - Notre Dame Journal of Formal Logic 50 (1):1-22.
An implementation of statistical default logic.Gregory Wheeler & Carlos Damasio - 2004 - In Jose Alferes & Joao Leite (eds.), Logics in Artificial Intelligence (JELIA 2004). Springer.
Defaults as restrictions on classical Hilbert-style proofs.Gianni Amati, Luigia Carlucci Aiello & Fiora Pirri - 1994 - Journal of Logic, Language and Information 3 (4):303-326.

Analytics

Added to PP
2014-01-16

Downloads
9 (#1,224,450)

6 months
2 (#1,232,442)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

A logic for default reasoning.Ray Reiter - 1980 - Artificial Intelligence 13 (1-2):81-137.
Circumscription — A Form of Non-Monotonic Reasoning.John McCarthy - 1980 - Artificial Intelligence 13 (1-2):27–39.
Non-monotonic logic I.Drew McDermott & Jon Doyle - 1980 - Artificial Intelligence 13 (1-2):41-72.
A logic of knowledge and justified assumptions.Fangzhen Lin & Yoav Shoham - 1992 - Artificial Intelligence 57 (2-3):271-289.
A comparative study of open default theories.Michael Kaminski - 1995 - Artificial Intelligence 77 (2):285-319.

View all 6 references / Add more references