Article contents
On the complexity of identifying head-elementary-set-free programs
Published online by Cambridge University Press: 13 November 2009
Abstract
Head-elementary-set-free (HEF) 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 HEF programs. This note solves the open problem by showing that the problem is complete for coNP.
Keywords
- Type
- Technical Note
- Information
- Copyright
- Copyright © Cambridge University Press 2009
References
- 3
- Cited by