We prove that -.unless the polynomial hierarchy collapses at the second level - the size of a purely propositional representation of the circumscription CIRC(T) of a propositional formula T grows faster than any polynomial as the size of T increases. We then analyze the significance of this result in the related field of closed-world reasoning.
On compact representations of propositional circumscription / Cadoli, M.; Donini, F. M.; Schaerf, M.. - 900:(1995), pp. 205-216. (Intervento presentato al convegno 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1995 tenutosi a Munich; Germany).
On compact representations of propositional circumscription
Cadoli M.;Donini F. M.;Schaerf M.
1995
Abstract
We prove that -.unless the polynomial hierarchy collapses at the second level - the size of a purely propositional representation of the circumscription CIRC(T) of a propositional formula T grows faster than any polynomial as the size of T increases. We then analyze the significance of this result in the related field of closed-world reasoning.File allegati a questo prodotto
| File | Dimensione | Formato | |
|---|---|---|---|
|
Cadoli_On-compact_1995.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
773.36 kB
Formato
Adobe PDF
|
773.36 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
