Forgetting is removing variables from a logical formula while preserving the constraints on the other variables. In spite of reducing information, it does not always decrease the size of the formula and may sometimes increase it. This article discusses the implications of such an increase and analyzes the computational properties of the phenomenon. Given a propositional Horn formula, a set of variables and a maximum allowed size, deciding whether forgetting the variables from the formula can be expressed in that size is Dp-hard in Σ2p. The same problem for unrestricted CNF propositional formulae is D2p-hard in Σ3p.
The ghosts of forgotten things: A study on size after forgetting / Liberatore, P.. - In: ANNALS OF PURE AND APPLIED LOGIC. - ISSN 0168-0072. - 175:8(2024). [10.1016/j.apal.2024.103456]
The ghosts of forgotten things: A study on size after forgetting
Liberatore P.
2024
Abstract
Forgetting is removing variables from a logical formula while preserving the constraints on the other variables. In spite of reducing information, it does not always decrease the size of the formula and may sometimes increase it. This article discusses the implications of such an increase and analyzes the computational properties of the phenomenon. Given a propositional Horn formula, a set of variables and a maximum allowed size, deciding whether forgetting the variables from the formula can be expressed in that size is Dp-hard in Σ2p. The same problem for unrestricted CNF propositional formulae is D2p-hard in Σ3p.| File | Dimensione | Formato | |
|---|---|---|---|
|
Liberatore_The-ghosts_2024.pdf
accesso aperto
Note: https://doi.org/10.1016/j.apal.2024.103456
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
735.59 kB
Formato
Adobe PDF
|
735.59 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
