Forest Logic Programs (FoLP) are a decidable fragment of Open Answer Set Programming (OASP) which have the forest model property. OASP extends Answer Set Programming (ASP) with open domains-a feature which makes it possible for FoLPs to simulate reasoning with the description logic SHOQ. In the past, several tableau algorithms have been devised to reason with FoLPs, the most recent of which established a NExpTimb upper bound for reasoning with the fragment. While known to be ExpTime-hard, the exact complexity characterization of reasoning with FoLPs was still unknown. In this paper we settle this open question by a reduction of reasoning with FoLPs to emptiness checking of fully enriched automata which are known to be ExpTime-complete.
展开▼
