# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

__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.)

## On Computing all Abductive Explanations from a Propositional Horn Theory

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: 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