Title: Complexity of First Order ID-Logic
Authors: Denecker, Marc #
Issue Date: 2-Jan-2008
Host Document: The Tenth International Symposium on Artificial Intelligence and Mathematics pages:1-15
Conference: ISAIM edition:10 location:Fot Launderdale date:2-4 January 2008
Abstract: First Order ID-Logic interprets general first order, non-monotone, inductive definability by generalizing the well-founded semantics for logic programs. We show that, for general (thus perhaps infinite)
structures, inference in First Order ID-Logic is complete Pi^1_2 over the natural numbers. We also prove a Skolem Theorem for the logic: every consistent formula of First Order ID-Logic has a countable model.
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
# (joint) last author

Files in This Item:
File Description Status SizeFormat
JSchlipf-ss1.pdfThe paper Published 162KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.