REACHABILITY ANALYSIS OF DYNAMICAL-SYSTEMS HAVING PIECEWISE-CONSTANT DERIVATIVES

被引：143

作者：

ASARIN, E

MALER, O

PNUELI, A

机构：

[1] VERIMAG, SPECTRE, F-38330 MONTBONNOT, FRANCE

[2] MOSCOW INFORMAT TRANSMISS PROBLEMS INST, MOSCOW, RUSSIA

[3] WEIZMANN INST SCI, DEPT COMP SCI, IL-76100 REHOVOT, ISRAEL

[4] UNIV PARIS 12, VAL DE MARNE, FRANCE

来源：

THEORETICAL COMPUTER SCIENCE | 1995年 / 138卷 / 01期

基金：

俄罗斯基础研究基金会;

关键词：

Number:; 6021; Acronym:; -; Sponsor:; РФФИ; Sponsor: Russian Foundation for Basic Research;

D O I：

10.1016/0304-3975(94)00228-B

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we consider a class of hybrid systems, namely dynamical systems with piecewise-constant derivatives (PCD systems). Such systems consist of a partition of the Euclidean space into a finite set of polyhedral sets (regions). Within each region the dynamics is defined by a constant vector field, hence discrete transitions occur only on the boundaries between regions when the trajectories change their direction. With respect to such systems we investigate the reachability question: Given an effective description of the systems and of two polyhedral subsets P and Q of the state-space, is there a trajectory starting at some x is an element of P and reaching some point in Q? Our main results are a decision procedure for two-dimensional systems, and an undecidability result for three or more dimensions.

引用

页码：35 / 65

页数：31