On the complexity of identifying Head Elementary Set Free programs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.
11 pages. To appear in Theory and Practice of Logic Programming (TPLP)

Keywords

Logic in Computer Science, Computational Complexity, F.3.1

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/231225

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0905.3802
 http://arxiv.org/abs/0905.3802

Collections

arXiv