On the complexity of identifying Head Elementary Set Free programs
| dc.creator | Fassetti, Fabio | |
| dc.creator | Palopoli, Luigi | |
| dc.date | 2009-05-25 | |
| dc.date.accessioned | 2026-07-07T13:17:46Z | |
| dc.date.available | 2026-07-07T13:17:46Z | |
| dc.description | Head-elementary-set-free programs were proposed in (Gebser et al. 2007) and shown to generalize over head-cycle-free programs while retaining their nice properties. It was left as an open problem in (Gebser et al. 2007) to establish the complexity of identifying head-elementary-set-free programs. This note solves the open problem, by showing that the problem is complete for co-NP. | |
| dc.description | 11 pages. To appear in Theory and Practice of Logic Programming (TPLP) | |
| dc.identifier | https://arxiv.org/abs/0905.3802 | |
| dc.identifier | http://arxiv.org/abs/0905.3802 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/231225 | |
| dc.subject | Logic in Computer Science | |
| dc.subject | Computational Complexity | |
| dc.subject | F.3.1 | |
| dc.title | On the complexity of identifying Head Elementary Set Free programs | |
| dc.type | text |