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, October 11, 2005, 12:15 pm

**Duration**: This information is not available in the database

**Location**: This information is not available in the database

**Speaker**: Ken Satoh (National Institute of Informatics, Japan)

We consider the problem of enumerating
minimally revised software
specifications in the situation where a
new specification is added to the current specification
and causes a conflict. We assume that a specification
is expressed as a set of Horn clauses which is divided into
two sets *Tpst* and *Ttmp* that are the unchangeable and
changeable parts of the specification, respectively.
Since a minimal revision is obtained by
removing a minimal set of clauses from *Ttmp* so that the
remaining set is consistent, our task can be restated as
enumerating maximal consistent subsets of a given set of Horn
clauses.
Moreover, consistency property is
monotone, that is, if a set of Horn clauses is consistent
then every
subset of the set is also consistent. Then, we can apply
our previous
method of enumerating maximal frequent sets in data
mining which can be used for
any enumeration for maximal subsets w.r.t. a monotone
property. We analyze this algorithm by query complexity
and sample complexity.

(This is a joint work with Takeaki Uno)

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