Hybrid automaton

In automata theory, a hybrid automaton (plural: hybrid automata or hybrid automatons) is a mathematical model for precisely describing systems in which digital computational processes interact with analog physical processes. A hybrid automaton is a finite state machine with a finite set of continuous variables whose values are described by a set of ordinary differential equations. This combined specification of discrete and continuous behaviors enables dynamic systems that comprise both digital and analog components to be modeled and analyzed.

Examples

A simple example is a room-thermostat-heater system where the temperature of the room evolves according to laws of thermodynamics and the state of the heater (on/off); the thermostat senses the temperature, performs certain computations and turns the heater on and off. In general, hybrid automata have been used to model and analyze a variety of embedded systems including vehicle control systems, air traffic control systems, mobile robots, and processes from systems biology.

Formal Definition

An Alur-Henzinger hybrid automaton H comprises the following components:[1]

So this is a labeled multidigraph.

Related models

Hybrid automata come in several flavors: The Alur-Henzinger hybrid automaton is a popular model; it was developed primarily for algorithmic analysis of hybrid systems model checking. The HyTech model checking tool is based on this model. The Hybrid Input/Output Automaton model has been developed more recently. This model enables compositional modeling and analysis of hybrid systems. Another formalism which is useful to model implementations of hybrid automaton is the lazy linear hybrid automaton. A sub-class of hybrid automata are timed automata in which all continuous variables have derivative 1. State reachability is decidable for this sub-class, which is why it is an interesting formalism for formal verification.

References

  1. Henzinger, T.A. "The Theory of Hybrid Automata". Proceedings of the Eleventh Annual IEEE Symposium on Logic in Computer Science (LICS), pages 278-292, 1996.

Further reading

This article is issued from Wikipedia - version of the Friday, March 18, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.