Efficient deadlock-freeness detection in real-time systems

A time-action-lock (TAL) is a state of a real-time system at which neither time can progress nor an action can occur. B. Behzad and O. Kozo presented a TAL-freeness detection method based on the geometry of timed automata. It is realized by means of translating the problem to rational Presburger sentences that has its drawback of inefficiency. In this paper, we present an algebraic approach for TAL-freeness detection, which can dramatically improve the performance of the method previously published. Detailed correctness proofs and performance analysis are provided.