ON THE EXPRESSIVENESS OF TEMPORAL LOGIC PROGRAMMING

In this paper, we address expressiveness issues for temporal logic programming, and in particular for the language TEMPLOG. We focus on the temporal component of the expressiveness by considering the propositional fragment of the language, which we call PTEMPLOG. We prove that PTEMPLOG is able to express positive least-fixpoint temporal properties, which (up to a convention concerning atomic formulas) corresponds to finitely regular omega-languages. Finally, we consider the extension of PTEMPLOG With stratified negation and we show that it is able to express all omega-regular languages. (C) 1995 Academic Press. Inc.