Cited By
View all- Felfernig AHotz LBagley CTiihonen J(2014)Knowledge-based ConfigurationundefinedOnline publication date: 14-Apr-2014
Redundancy in logic III: Non-monotonic reasoning
Pages 1317 - 1359
Abstract
Results about the redundancy of certain versions of circumscription and default logic are presented. In particular, propositional circumscription where all variables are minimized and skeptical default logics are considered. This restricted version of circumscription is shown to have the unitary redundancy property: a CNF formula is redundant (it is equivalent to one of its proper subsets) if and only if it contains a redundant clause (it is equivalent to itself minus one clause); default logic does not have this property in general. We also give the complexity of checking redundancy in the considered formalisms.
References
[1]
Ausiello, G., D'Atri, A. and Saccà, D., Minimal representation of directed hypergraphs. SIAM Journal on Computing. v15 i2. 418-431.]]
[2]
Antoniou, G., A tutorial on default logics. ACM Computing Surveys. v31 i4. 337-359.]]
[3]
Antoniou, G. and Sperschneider, V., Operational concepts of non-monotonic logics, part 1: Default logic. Artificial Intelligence Review. v8 i1. 3-16.]]
[4]
Besnard, P., An Introduction to Default Logic. 1989. Springer, Berlin.]]
[5]
Bruni, R., Approximating minimal unsatisfiable subformulae by means of adaptive core search. Discrete Applied Mathematics. v130 i2. 85-100.]]
[6]
Bossu, P. and Siegel, P., Saturation, non-monotonic reasoning and the closed world assumption. Artificial Intelligence. v25. 16-63.]]
[7]
Büning, H. and Zhao, X., Extension and equivalence problems for clause minimal formulae. Annals of Mathematics and Artificial Intelligence. v43 i1. 295-306.]]
[8]
Cadoli, M., Eiter, T. and Gottlob, G., Default logic as a query language. IEEE Transactions on Knowledge and Data Engineering. v9 i3. 448-463.]]
[9]
de Kleer, J. and Konolige, K., Eliminating the fixed predicates from a circumscription. Artificial Intelligence. v39. 391-398.]]
[10]
Delgrande, J. and Schaub, T., Expressing default logic variants in default logic. Journal of Logic and Computation. v15 i5. 593-621.]]
[11]
Delgrande, J.P., Schaub, T. and Jackson, W.K., Alternative approaches to default logic. Artificial Intelligence. v70. 167-237.]]
[12]
T. Eiter, M. Fink, H. Tompits, S. Woltran, Strong and uniform equivalence in answer-set programming: Characterizations and complexity results for the non-ground case, in: Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI 2005), 2005, pp. 695--700]]
[13]
Eiter, T. and Gottlob, G., Propositional circumscription and extended closed world reasoning are Π2p-complete. Theoretical Computer Science. v114. 231-245.]]
[14]
Fleischner, H., Kullmann, O. and Szeider, S., Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. Theoretical Computer Science. v289. 503-516.]]
[15]
C. Froidevaux, J. Mengin, A framework for default logics, in: European Workshop on Logics in AI (JELIA'92), 1992, pp. 154--173]]
[16]
Froidevaux, C. and Mengin, J., Default logics: A unified view. Computational Intelligence. v10. 331-369.]]
[17]
Gottlob, G. and Fermüller, C.G., Removing redundancy from a clause. Artificial Intelligence. v61. 263-289.]]
[18]
A. Ginsberg, Knowledge base reduction: A new approach to checking knowledge bases for inconsistency & redundancy, in: Proceedings of the Seventh National Conference on Artificial Intelligence (AAAI'88), 1988, pp. 585--589]]
[19]
Giordano, L. and Martelli, A., On cumulative default logics. Artificial Intelligence. v66. 161-179.]]
[20]
Gottlob, G., Complexity results for non-monotonic logics. Journal of Logic and Computation. v2. 397-425.]]
[21]
Gottlob, G., Translating default logic into standard autoepistemic logic. Journal of the ACM. v42. 711-740.]]
[22]
Hammer, P. and Kogan, A., Optimal compression of propositional Horn knowledge bases: Complexity and approximation. Artificial Intelligence. v64 i1. 131-145.]]
[23]
E. Hemaspaandra, G. Wechsung, The minimization problem for Boolean formulas, in: Proceedings of the Thirty Eighth Annual Symposium on the Foundations of Computer Science (FOCS'97), 1997, pp. 575--584]]
[24]
Janhunen, T., Evaluating the effect of semi-normality on the expressiveness of defaults. Artificial Intelligence. v144. 233-250.]]
[25]
L. Kirousis, P. Kolaitis, A dichotomy in the complexity of propositional circumscription, in: Proceedings of the Nineteenth IEEE Symposium on Logic in Computer Science (LICS 2004), 2001, pp. 71--80]]
[26]
Liberatore, P., Redundancy in logic I: CNF propositional formulae. Artificial Intelligence. v163 i2. 203-232.]]
[27]
Liberatore, P., Representability in default logic. Logic Journal of the IGPL. v13 i3. 335-351.]]
[28]
Liberatore, P., On the complexity of extension checking in default logic. Information Processing Letters. v98 i2. 61-65.]]
[29]
Liberatore, P., Where fail-safe default logics fail. ACM Transactions on Computational Logic. v8 i2.]]
[30]
Liberatore, P., Redundancy in logic II: 2-CNF and Horn propositional formulae. Artificial Intelligence. v172 i2--3. 265-299.]]
[31]
J. Lang, P. Marquis, In search of the right extension, in: Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2000), 2000, pp. 625--636]]
[32]
Lifschitz, V., Pearce, D. and Valverde, A., Strongly equivalent logic programs. ACM Transactions on Computational Logic. v2 i4. 526-541.]]
[33]
Lukaszewicz, W., Considerations on default logic: An alternative approach. Computational Intelligence. v4 i1. 1-16.]]
[34]
Maier, D., Minimum covers in relational database model. Journal of the ACM. v27 i4. 664-674.]]
[35]
Makinson, D., General theory of cumulative inference. In: Proceedings of the Second International Workshop on Non-Monotonic Reasoning, Springer. pp. 1-18.]]
[36]
McCarthy, J., Circumscription---A form of non-monotonic reasoning. Artificial Intelligence. v13. 27-39.]]
[37]
A. Meyer, L. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, in: Proceedings of the Thirteenth Annual Symposium on Switching and Automata Theory (FOCS'72), 1972, pp. 125--129]]
[38]
Marek, W. and Truszczyński, M., Non-Monotonic Logics: Context-Dependent Reasoning. 1993. Springer, Berlin.]]
[39]
A. Mikitiuk, M. Truszczynski, Constrained and rational default logics, in: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI'95), 1995, pp. 1509--1517]]
[40]
G. Nordh, P. Jonsson, An algebraic approach to the complexity of propositional circumscription, in: Proceedings of the Nineteenth IEEE Symposium on Logic in Computer Science (LICS 2004), 2004, pp. 367--376]]
[41]
Poole, D.L., A logical framework for default reasoning. Artificial Intelligence. v36. 27-47.]]
[42]
Poole, D., Default logic. In: Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 3: Non-Monotonic and Uncertainty Reasoning, Oxford University Press, Oxford. pp. 189-215.]]
[43]
Papadimitriou, C. and Wolfe, D., The complexity of facets resolved. Journal of Computer and System Sciences. v37. 2-13.]]
[44]
Reiter, R., A logic for default reasoning. Artificial Intelligence. v13. 81-132.]]
[45]
R. Rosati, Model checking for non-monotonic logics, in: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI'99), 1999, pp. 76--83]]
[46]
T. Schaub, On constrained default theories, in: Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI'92), 1992, pp. 304--308]]
[47]
P. Siegel, L. Forget, A representation theorem for preferential logics, in: Proceedings of the Fifth International Conference on the Principles of Knowledge Representation and Reasoning (KR'96), 1996, pp. 453--460]]
[48]
J. Schmolze, W. Snyder, Detecting redundant production rules, in: Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI'97), 1997, pp. 417--423]]
[49]
J. Stillman, The complexity of propositional default logics, in: Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI'92), 1992, pp. 794--799]]
[50]
Truszczynski, M., Strong and uniform equivalence of non-monotonic theories---an algebraic approach. Annals of Mathematics and Artificial Intelligence. v48 i3--4. 245-265.]]
[51]
H. Turner, Strong equivalence for logic programs and default theories (made easy), in: Proceedings of the Sixth International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR'01), 2001, pp. 81--92]]
[52]
C. Umans, The minimum equivalent DNF problem and shortest implicants, in: Proceedings of the Thirty Ninth Annual Symposium on the Foundations of Computer Science (FOCS'98), 1998, pp. 556--563]]
Index Terms
- Redundancy in logic III: Non-monotonic reasoning
Recommendations
Reasoning under minimal upper bounds in propositional logic
Reasoning from the minimal models of a theory, as fostered by circumscription, is in the area of Artificial Intelligence an important method to formalize common sense reasoning. However, as it appears, minimal models may not always be suitable to ...
Sequent calculi for propositional nonmonotonic logics
A uniform proof-theoretic reconstruction of the major nonmonotonic logics is introduced. It consists of analytic sequent calculi where the details of nonmonotonic assumption making are modelled by an axiomatic rejection method. Another distinctive ...
From answer set logic programming to circumscription via logic of GK
We first embed Pearce's equilibrium logic and Ferraris's propositional general logic programs in Lin and Shoham's logic of GK, a nonmonotonic modal logic that has been shown to include as special cases both Reiter's default logic in the propositional ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V. © 2008.
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 01 July 2008
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Nov 2024
Other Metrics
Citations
Cited By
View all- Felfernig AHotz LBagley CTiihonen J(2014)Knowledge-based ConfigurationundefinedOnline publication date: 14-Apr-2014
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in