Decidability and definability with circumscription

DOI10.1016/0168-0072(87)90062-5zbMath0625.03017OpenAlexW2055029276MaRDI QIDQ579240

John S. Schlipf

Publication date: 1987

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(87)90062-5

zbMATH Keywords

dynamic logicexpressive powercountable modelscircumscriptionminimal modeleveryday reasoninginfinite model

Mathematics Subject Classification ID

Artificial intelligence (68T99) Decidability of theories and sets of sentences (03B25) Second- and higher-order model theory (03C85)

Related Items

Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete, Circumscribing DATALOG: expressive power and complexity, Complexity and undecidability results for logic programming, Is intractability of nonmonotonic reasoning a real drawback?, Generalized closed world assumption is \(\Pi ^ 0_ 2\)-complete, An efficient method for eliminating varying predicates from a circumscription, Sequent calculi for skeptical reasoning in predicate default logic and other nonmonotonic logics, The complexity of predicate default logic over a countable domain

Cites Work

• Unnamed Item
• Unnamed Item
• On the satisfiability of circumscription
• Completeness results for circumscription
• Descriptive set theory
• Circumscription - a form of non-monotonic reasoning
• The mathematics of non-monotonic reasoning
• Definability in dynamic logic
• Elementary induction on abstract structures