A Decidable Class of Planar Linear Hybrid Systems

Pavithra Prabhakar, Vladimeros Vladimerou, Mahesh Viswanathan and Geir E. Dullerud

In this paper, we show the decidability of a new subclass of linear hybrid automata. These automata are planar, that is, consist of two state variables, monotonic along some direction in the plane and have identity resets, that is, the values of the con- tinuous variables are not reset to a different value on a discrete transition. Our proof uses a combination of a tree construction capturing the edge-to-edge reach- ability and a finite bisimulation construction. Our class strictly contains the class of two dimensional piecewise constant derivative systems for which decidability of the reachability problem is known.

Theoretical Computer Science (TCS), 2015
Download: BIB PS PDF

Back