| Autor: | Jean-Jacques Hébrard, Emmanuel Benoist |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Discrete mathematics
Class (set theory) French horn Applied Mathematics Quantum Physics Propositional calculus Polynomial algorithm Artificial Intelligence Simple (abstract algebra) Computer Science::Logic in Computer Science Bounded function Calculus Polynomial delay Recognition algorithm Mathematics |
| Zdroj: | Annals of Mathematics and Artificial Intelligence. 37:251-272 |
| ISSN: | 1012-2443 |
| DOI: | 10.1023/a:1021243928374 |
| Popis: | The enlarged Horn formulas generalize the extended Horn formulas introduced by Chandru and Hooker (1991). Their satisfying truth assignments can be generated with polynomial delay. Unfortunately no polynomial algorithm is known for recognizing enlarged Horn formulas or extended Horn formulas. In this paper we define the class of simple enlarged Horn formulas, a subclass of the enlarged Horn formulas, that contains the simple extended Horn formulas introduced by Swaminathan and Wagner (1995). We present recognition algorithms for the simple enlarged Horn formulas and the simple extended Horn formulas whose complexity is bounded by the complexity of the arborescence-realization problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink