Title: Formalizing Timing Diagram Requirements in Discrete Duration Calulus,
Abstract: Several temporal logics have been proposed to formalise timing diagram
requirements over hardware and embedded controllers. These include LTL,
discrete time MTL and the recent industry standard PSL. However, succintness
and visual structure of a timing diagram are not adequately captured by their
formulae. Interval temporal logic QDDC is a highly succint and visual notation
for specifying patterns of behaviours.
In this paper, we propose a practically useful notation called SeCeCntnl
which enhances negation free fragment of QDDC with features of nominals and
limited liveness. We show that timing diagrams can be naturally
(compositionally) and succintly formalized in SeCeCntnl as compared with PSL
and MTL. We give a linear time translation from timing diagrams to SeCeCntnl.
As our second main result, we propose a linear time translation of SeCeCntnl
into QDDC. This allows QDDC tools such as DCVALID and DCSynth to be used for
checking consistency of timing diagram requirements as well as for automatic
synthesis of property monitors and controllers. We give examples of a minepump
controller and a bus arbiter to illustrate our tools. Giving a theoretical
analysis, we show that for the proposed SeCeCntnl, the satisfiability and model
checking have elementary complexity as compared to the non-elementary
complexity for the full logic QDDC.