94 citations · 246 across the 28 of their papers we have counts for
Showing 2005Show all
3 papers · 1 filter
cs.LO2005★ 12 cited
Redundancy in Logic III: Non-Mononotonic Reasoning
Paolo Liberatore
Results about the redundancy of circumscriptive and default theories are presented. In particular, the complexity of establishing whether a given theory is redundant is establihsed…
cs.AI2005★ 26 cited
Redundancy in Logic II: 2CNF and Horn Propositional Formulae
Paolo Liberatore
We report complexity results about redundancy of formulae in 2CNF form. We first consider the problem of checking redundancy and show some algorithms that are slightly better than…
cs.AI2005★ 6 cited
Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems
Paolo Liberatore
We study the problem of deciding whether some PSPACE-complete problems have models of bounded size. Contrary to problems in NP, models of PSPACE-complete problems may be exponentia…