DISCRETE-CONTINUOUS SYSTEMS - AN ALGORITHMIC ASPECT

This work deals with the relation between discrete and continuous syst ems and examines the issue of the ability of a continuous system to se rve as a model of a discrete system. particular attention is given to dynamic systems, namely, the systems with piecewise-constant derivativ es (PCDS). These systems are preset by differential equations with pie cewise-constant right sides, which is typical for continuous systems u sing discrete controllers. It is shown that any Turing machine can be simulated by means of a PCDS of dimension 3. On the other hand, in the case of dimension 2, it is impossible to simulate the functioning of some finite automata. In the basic part of this paper, algorithmic iss ues relating to PCDS's are treated. In [O. Maler and A. Pnueli, ''Reac hability analysis of planar multi-linear systems, ''Proc. of the 5th W orkshop on computer-Aided Verification, Elounda, Greece, Lect. Notes C omp. Sci., 697, Springer-Verlag, 194-209 (1993)], Malero and Pnueli su ggest an algorithm designed to investigate completely the behavior of a PCDS on a plane, in particular, to solve the reachability problem fo r a system of this type. From the simulation results presented at the first stage of our discussion it follows that this problem for three-d imensional PCS's algorithmically undecidable.