Conflict-Tolerant Specifications for Hybrid Systems

Deepak D'Souza, Madhu Gopinathan, Ramesh S, Prahladavaradan Sampath


We propose a framework for developing and reasoning about hybrid systemsthat are comprised of a plant with multiple controllers, each of which controls theplant intermittently. The framework is based on the notion of a “conflict-tolerant” specification for a controller, and provides a modular way of developing and reasoningabout such systems. We propose a novel mechanism of defining conflicttolerantspecifications for general hybrid systems, using “acceptor” and “advisor” components. We also give a decision procedure for verifying whether a controllersatisfies its conflict-tolerant specification, in the special case when the componentsare modeled using initialized rectangular hybrid automata.

Full Text:



Rajeev Alur, Costas Courcoubetis, Nicolas Halbwachs, Thomas A. Henzinger, Pei-Hsin Ho, Xavier Nicollin, Alfredo Olivero, Joseph Sifakis, and Sergio Yovine. The algorithmic analysis of hybrid systems. Theor. Comput. Sci., 138(1):3–34, 1995.

Rajeev Alur and David L. Dill. A theory of timed automata. Theor. Comput. Sci., 126(2):183–235, 1994.

Rajeev Alur, Thomas A. Henzinger, Gerardo Lafferriere, and George J. Pappas. Discrete abstractions of hybrid systems. Proc. of the IEEE, 88(7):971–984, Jul 2000.

E. Asarin, O. Bournez, T. Dang, O. Maler, and A. Pnueli. Effective synthesis of switching controllers for linear systems. Proc. of the IEEE, 88(7):1011–1025, Jul 2000.

Y. L. Chen, S. Lafortune, and F. Lin. Modular supervisory control with priorities for discrete event systems. In Conf. on Decision and Control, pages 409–415. IEEE, 1995.

Deepak D’Souza and Madhu Gopinathan. Conflict-tolerant features. In Computer Aided Verification, pages 227–239, 2008.

Deepak D’Souza, Madhu Gopinathan, S. Ramesh, and Prahladavaradan Sampath. Conflict-tolerant real-time features. In Quantitative Evaluation of Systems, pages

–283, 2008.

Deepak D’Souza, Madhu Gopinathan, S. Ramesh, and Prahladavaradan Sampath. Supervisory control for real-time systems based on conflict-tolerant controllers. In Conference on Automation Science and Engineering, 2009.

Amy P. Felty and Kedar S. Namjoshi. Feature specification and automated conflict detection. ACM Trans. Softw. Eng. Methodol., 12(1):3–27, 2003.

Kathi Fisler and Shriram Krishnamurthi. Decomposing verification by features. IFIP Working Conference on Verified Software: Theories, Tools, Experiments, 2006.

Madhu Gopinathan. Conflict Tolerant Features. PhD thesis, Department of Computer Science and Automation, Indian Institute of Science, Bangalore, Oct 2009.18

Jonathan D. Hay and Joanne M. Atlee. Composing features and resolving interactions. In SIGSOFT Found. of Softw. Engg., pages 110–119, 2000.

Thomas A. Henzinger, Peter W. Kopke, Anuj Puri, and Pravin Varaiya. What’s decidable about hybrid automata? J. Comput. Syst. Sci., 57(1):94–124, 1998.

Dirk O. Keck and Paul J. K¨uhn. The feature and service interaction problem in telecommunications systems. a survey. IEEE Trans. Software Eng., 24(10):779–796, 1998.

MSNBC. The top 10 safety features for the future – http://www.msnbc.msn. com/id/23300261, 2008.

Rajesh Rajamani. Vehicle Dynamics and Control. Springer, 2006.

Peter J. G. Ramadge and W. Murray Wonham. The control of discrete event systems. In Proc. of the IEEE, volume 77, pages 81–98, 1989.

C.J. Tomlin, J. Lygeros, and S. Shankar Sastry. A game theoretic approach to controller design for hybrid systems. Proc. of the IEEE, 88(7):949–970, Jul 2000.

K. C. Wong, J. G. Thistle, H. H. Hoang, and R. P. Malham´e. Supervisory control of distributed systems: Conflict resolution. In Conf. on Decision and Control, pages 416–421. IEEE, 1995.


  • There are currently no refbacks.