A first order logic for specification of timed algorithms: basic properties and a decidable class

• Published in: Annals of pure and applied logic 2002-01, Vol.113 (1), p.13-52
• Main Authors: Beauquier, Danièle, Slissenko, Anatol
• Format: Article
• Language: English
• Subjects: Decidability; First order logic; Specification; Timed algorithms
• ISSN: 0168-0072
• DOI: 10.1016/S0168-0072(01)00049-5

We consider one aspect of the problem of specification and verification of reactive real-time systems which involve operations and constraints concerning time. Time is continuous what is motivated by specifications of hybrid systems. Our goal is to try to find a framework that is based on applied first order logic that permits to represent the verification problem directly, completely and conservatively (as explained in Introduction), and that is apt to describe interesting decidable classes, maybe showing way to feasible algorithms. To achieve this goal we use a first order timed logic that is an extension of a decidable theory of reals with timed functions. This logic permits, on the one hand, to rewrite directly and completely requirements and, on the other hand, to describe executions of various timed algorithms—here we consider block Gurevich abstract state machines because of their theoretical clarity and sufficient expressive power. Then we describe one decidable class of the verification problem that is based on notions reflecting finiteness properties of systems of control. These notions may be of independent interest, as, in particular, they give a way to describe a limited usage of arithmetics preserving decidability that is not covered by existing model-theoretic approaches. As an example we consider the generalized railroad crossing problem that we analyze in its entirety.