Abstract
Current Answer Set Programming systems are built on non-monotonic logic programs without function symbols; as well-known, they lead to high undecidability in general. However, function symbols are highly desirable for various applications, which challenges to find meaningful and decidable fragments of this setting. We present the class FDNC of logic programs which allows for function symbols, disjunction, non-monotonic negation under answer set semantics, and constraints, while still retaining the decidability of the standard reasoning tasks. Thanks to these features, they are a powerful formalism for rule-based modeling of applications with potentially infinite processes and objects, which allows also for common-sense reasoning. We show that consistency checking and brave reasoning are ExpTime-complete in general, but have lower complexity for restricted fragments, and outline worst-case optimal reasoning procedures for these tasks. Furthermore, we present a finite representation of the possibly infinitely many infinite stable models of an FDNC program, which may be exploited for knowledge compilation purposes.

URL:
http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2007-143

BibTeX:

@inproceedings{REWERSE-RP-2007-143,
	author = {Mantas Šimkus and Thomas Eiter},
	title = {FDNC: Decidable Non-monotonic Disjunctive Logic Programs with Function Symbols},
	booktitle = {Proceedings of 14th International Conference on Logic for Programming Artificial Intelligence and Reasoning, Yerevan, Armenia (15th--19th October 2007)},
	year = {2007},
	volume = {4790},
	series = {LNCS},
	pages = {514--530},
	url = {http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2007-143}
}