On the Feasibility of Checking Temporal Integrity Constraints

摘要

We analyze the computational feasibility of checking temporal integrity constraints formulated in some sublanguages of first-order temporal logic. Our results illustrate the impact of the quantifier pattern on the complexity of this problem. The presence of a single quantifier in the scope of a temporal operator makes the problem undecidable. On the other hand, if no quantifiers are in the scope of a temporal operator and all the quantifiers are universal, temporal integrity checking can be done in exponential time.