The Theory of Timed I / O Automata

This monograph presents the timed input/output automaton (TIOA) modeling framework, a basic mathematical framework to support description and analysis of timed (computing) systems. Timed systems are systems in which desirable correctness or performance properties of the system depend on the timing of events, not just on the order of their occurrence. Timed systems are employed in a wide range of domains including communications, embedded systems, real-time operating systems, and automated control. Many applications involving timed systems have strong safety, reliability, and predictability requirements, which make it important to have methods for systematic design of systems and rigorous analysis of timing-dependent behavior.Designers of real-time systems or timing-based algorithms can use the TIOA framework to describe complex systems and to decompose them into manageable pieces. This framework is a natural basis for computerized modeling and analysis.This lecture includes:" Mathematical preliminaries" Definitions of external behavior for timed automata and implementation and simulation relationships between them" Trajectories and timed sequences, which are useful for describing the behavior of timed systems" Composition and hiding operations for timed automata, along with operations for adding bounds that relate TIOAs to other timed automaton modelsCompositionality results for TIOAs as well as special classes of progressive and receptive TIOAs