1,721,030 research outputs found
Proceedings of Third International Symposium onGames, Automata, Logics and Formal Verification (GandALF 2012)
No full text
Automatic synthesis of switching controllers for linear hybrid systems: Safety control
No full textIn this paper we study the problem of automatically generating switching controllers for the class of Linear Hybrid Automata, with respect to safety objectives. While the same problem has been already considered in the literature, no sound and complete solution has been provided so far. We identify and solve inaccuracies contained in previous characterizations of the problem, providing a sound and complete symbolic fixpoint procedure to compute the set of states from which a controller can keep the system in a given set of desired states. While the overall procedure may not terminate, we prove the termination of each iteration, thus paving the way to an effective implementation
Linear and Branching System Metrics
No full textWe extend the classical system relations of trace inclusion, trace equivalence, simulation, and bisimulation to a quantitative setting in which propositions are interpreted not as boolean values, but as elements of arbitrary metric spaces. Trace inclusion and equivalence give rise to asymmetrical and symmetrical linear distances, while simulation and bisimulation give rise to asymmetrical and symmetrical branching distances. We study the relationships among these distances, and we provide a full logical characterization of the distances in terms of quantitative versions of LTL and mu-calculus. We show that, while trace inclusion (resp. equivalence) coincides with simulation (resp. bisimulation) for deterministic boolean transition systems, linear and branching distances do not coincide for deterministic metric transition systems. Finally, we provide algorithms for computing the distances over finite systems, together with a matching lower complexity bound
Automatic Synthesis of Switching Controllers for Linear Hybrid Systems: Reachability Control
No full textWe consider the problem of computing the controllable region of a Linear Hybrid Automaton with controllable and uncontrollable transitions, w.r.t. a reachability objective. We provide an algorithm for the finite-horizon version of the problem, based on computing the set of states that must reach a given non-convex polyhedron while avoiding another one, subject to a polyhedral constraint on the slope of the trajectory. Experimental results are presented, based on an implementation of the proposed algorithm on top of the tool SpaceEx.</jats:p
- …
