×

Restricted default theories: expressive power and outlier detection tasks. (English) Zbl 1318.68168

Summary: We study the tractability frontier of outlier detection problems, by analyzing it with respect to \((i)\) the considered outlier detection problem, \((ii)\) the reference default logic fragment, and \((iii)\) the adopted notion of outlier. As for point \((i)\), we shall consider three problems of increasing complexity, called Outlier-Witness Recognition, Outlier Recognition and Outlier Existence, respectively. As for point \((ii)\), as we look for conditions under which outlier detection can be done efficiently, attention will be limited to subsets of Disjunction-free propositional default theories. As for point \((iii)\), we shall refer to both the notion of outlier introduced in [the first author et al., Artif. Intell. 172, No. 16–17, 1837–1872 (2008; Zbl 1184.68480)] and a new and more restrictive one, called strong outlier. We also present a polynomial time algorithm for enumerating all strong outliers of bounded size in a quasi-acyclic normal unary default theory. Some of our tractability results rely on the Incremental Lemma that provides conditions for a default logic fragment to have a monotonic behavior. Finally, in order to show that the simple fragments of DL we deal with are still rich enough to solve interesting problems and, therefore, that the tractability results that we prove are interesting not merely on the theoretical side, insights into the expressive capabilities of these fragments are provided, by showing that normal unary theories express all NL queries, hereby indirectly answering a question raised by H. A. Kautz and B. Selman [Artif. Intell. 49, No. 1–3, 243–279 (1991; Zbl 0736.68044)].

MSC:

68T27 Logic in artificial intelligence
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abiteboul, S.; Hull, R.; Vianu, V., Foundations of Databases (1995), Addison-Wesley · Zbl 0848.68031
[2] Angiulli, F.; Ben-Eliyahu-Zohary, R.; Ianni, G.; Palopoli, L., Computational properties of metaquerying problems, ACM Trans. Comput. Log., 4, 149-180 (2003) · Zbl 1365.68195
[3] Angiulli, F.; Ben-Eliyahu-Zohary, R.; Palopoli, L., Outlier detection using default reasoning, Artificial Intelligence, 172, 1837-1872 (2008) · Zbl 1184.68480
[4] Angiulli, F.; Ben-Eliyahu-Zohary, R.; Palopoli, L., Outlier detection for simple default theories, Artificial Intelligence, 174, 1247-1253 (2010) · Zbl 1210.68109
[5] Ben-Eliyahu, R.; Dechter, R., Propositional semantics for disjunctive logic programs, Ann. Math. Artif. Intell., 12, 53-87 (1994) · Zbl 0858.68012
[6] Ben-Eliyahu-Zohary, R., Yet some more complexity results for default logic, Artificial Intelligence, 139, 1-20 (2002) · Zbl 1013.03025
[7] Ben-Eliyahu-Zohary, R.; Gudes, E.; Ianni, G., Metaqueries: semantics, complexity, and efficient algorithms, Artificial Intelligence, 149, 61-87 (2003) · Zbl 1082.68598
[8] Beyersdorff, O.; Meier, A.; Müller, S.; Thomas, M.; Vollmer, H., Proof complexity of propositional default logic, Arch. Math. Logic, 50, 727-742 (2011) · Zbl 1308.03057
[9] Beyersdorff, O.; Meier, A.; Thomas, M.; Vollmer, H., The complexity of reasoning for fragments of default logic, J. Logic Comput., 22, 587-604 (2012) · Zbl 1267.68222
[10] Cadoli, M.; Eiter, T.; Gottlob, G., Default logic as a query language, IEEE Trans. Knowl. Data Eng., 9, 448-463 (1997)
[11] Dantsin, E.; Eiter, T.; Gottlob, G.; Voronkov, A., Complexity and expressive power of logic programming, ACM Comput. Surv., 33, 374-425 (2001)
[12] Duval, B.; Nicolas, P., Learning default theories, (ESCQARU (1999)), 148-159
[13] Ebbinghaus, H. D.; Flum, J., Finite Model Theory, Perspectives in Mathematical Logic (1995), Springer
[14] Gottlob, G., Complexity results for nonmonotonic logics, J. Logic Comput., 2, 397-425 (1992) · Zbl 0765.03012
[15] Johnson, D. S., A catalog of complexity classes, (Handbook of Theoretical Computer Science, vol. a (1990), MIT Press: MIT Press Cambridge, MA, USA), 67-161 · Zbl 0900.68246
[16] Kautz, H. A.; Selman, B., Hard problems for simple default logics, Artificial Intelligence, 49, 243-279 (1991) · Zbl 0736.68044
[17] Meier, A.; Schmidt, J.; Thomas, M.; Vollmer, H., On the parameterized complexity of default logic and autoepistemic logic, (Dediu, A. H.; Martn-Vide, C., LATA (2012), Springer), 389-400 · Zbl 1351.68120
[18] (Minker, J., Logic-Based Artificial Intelligence (2000), Kluwer Academic Publisher) · Zbl 0979.68095
[19] Neapolitan, R.; Xia, J., Contemporary Artificial Intelligence (2012), Chapman & Hall/CRC
[20] Papadimitriou, C. H., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0833.68049
[21] Poole, D.; Mackworth, A. K.; Goebel, R., Computational Intelligence - A Logical Approach (1998), Oxford University Press: Oxford University Press New York · Zbl 0926.68104
[22] Reiter, R., A logic for default reasoning, Artificial Intelligence, 13, 81-132 (1980) · Zbl 0435.68069
[23] Russell, S. J.; Norvig, P., Artificial Intelligence: A Modern Approach (2003), Prentice Hall: Prentice Hall Upper Saddle River, New Jersey
[24] Shen, W.; Ong, K.; Mitbander, B.; Zaniolo, C., Metaqueries for data mining, (Fayyad, U. M.; Piatetsky-Shapiro, G.; Smyth, P.; Uthurusamy, R., Advances in Knowledge Discovery and Data Mining (1996), AAAI Press/MIT Press), 375-398
[25] Stillman, J., The complexity of propositional default logics, (AAAI (1992)), 794-799
[26] Winston, P. H., Artificial Intelligence (1998), Addison-Wesley: Addison-Wesley Reading, Massachusetts
[27] Zhang, A.; Marek, W., On the classification and existence of structures in default logic, Fund. Inform., 13, 485-499 (1990) · Zbl 0810.03019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.