On checking parallel real-time systems for linear duration invariants

In this paper we define timed regular expressions to describe the timed behaviour of parallel real-time systems and consider the problem of checking algorithmically the set of timed behaviours defined by timed regular expressions for a real-time requirement specified by a linear duration invariant. In general, the problem can be solved by using the mixed integer linear programming techniques. We show that in many cases, the problem can be reduced to a finite number of linear programming problems