Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Mittagsseminar Talk Information |
Date and Time: Tuesday, November 02, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Kazuhisa Makino (Osaka Univ.)
Abduction is a fundamental mode of reasoning, which has applications in many areas of AI and Computer Science. The computation of abductive explanations is an important computational problem, which is at the core of early systems such as the ATMS and Clause Management Systems, and is intimately related to prime implicate generation in propositional logic. In this talk, we consider the problem of computing multiple explanations, and in particular all explanations for an abductive query from a propositional Horn theory. Our study pays particular attention to the form of the query, ranging from a literal to a compound formula, to whether explanations are based on a set of abducible literals, and to the representation of the Horn theory, either by a Horn CNF or model-based in terms of its characteristic models. For all these combinations, we present either tractability results in terms of polynomial total-time algorithms, intractability results in terms of nonexistence of such algorithms (unless P=NP), or semi-tractability results in terms of solvability in quasi-polynomial time, established by polynomial-time equivalence to the problem of dualizing a monotone conjunctive normal form expression. Our results complement previous results in the literature, and refute a longstanding conjecture by Selman and Levesque. They elucidate the complexity of generating all abductive explanations, and shed light on the related problems such as generating sets of restricted prime implicates of a Horn theory. The algorithms for tractable cases can be readily applied for generating a polynomial subset of explanations in polynomial time.
(Joint work with Thomas Eiter)
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2025 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.4803M | admin login