- News
- Subject and Goals
- Council and Annual Reports
- Contacts and Working Groups
- Lectures and Presentations
- Conferences and Seminars
- Publications
- Application Demos
- International Travels
- Visitors
- Past Events
- E-Synergy Login
SEARCH
MEMBERS OF RESEARCH CENTER
Research Centre
Data - Algorithms - Decision Making
Data - Algorithms - Decision Making
Established in 2005 under support of MŠMT ČR (project 1M0572)
Lectures and Presetations
A subclass of Horn CNFs optimally compressible in polynomial time
Lecturer:
Čepek O.
From:
Apr. 27 2009 2:00PM
To:
Apr. 27 2009 3:30PM
Place:
místnost č.203, ÚTIA AV ČR
Description:
The problem of Horn Minimization (HM) can be stated as follows: given a Horn CNF representing a Boolean function f, find a CNF representation of f which consists of a minimum possible number of clauses. This is a classical combina-torial optimization problem with many practical applications. For instance, the problem of knowledge compression for speeding up queries to propositional Horn expert systems is equivalent to HM.
HM is a computationally diffcult problem: it is known to be NP-hard even if the input is restricted to cubic Horn CNFs. On the other hand, there are two subclasses of Horn CNFs for which HM is known to be solvable in polynomial time: acyclic and quasi-acyclic Horn CNFs. In this talk we introduce a new class of Horn CNFs which properly contains both of the known classes and describe a polynomial time HM algorithm for this new class.
HM is a computationally diffcult problem: it is known to be NP-hard even if the input is restricted to cubic Horn CNFs. On the other hand, there are two subclasses of Horn CNFs for which HM is known to be solvable in polynomial time: acyclic and quasi-acyclic Horn CNFs. In this talk we introduce a new class of Horn CNFs which properly contains both of the known classes and describe a polynomial time HM algorithm for this new class.
Contact person:
Within the event:
Pravidelný seminář Inteligentní systémy (Contact person: Tomáš Kroupa)