Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Timed automaton
open-in-new
<p>A timed automaton is a mathematical model in <a href="/facts/Automata_theory/Q6BmPv63">automata theory</a> that extends <a href="/facts/Finite_automaton/GMusWd0a">finite automata</a> with a finite set of real-valued clocks. This <a href="/facts/Formal_system/KaeDAjK7">formalism</a>, introduced by <a href="/facts/Rajeev_Alur/VFPekza1">Rajeev Alur</a> and <a href="/facts/David_L._Dill/NwTYvLsU">David Dill</a> in 1994, enables the modeling of systems where timing constraints are crucial. </p><p>In a timed automaton, all clock values increase uniformly with passing time. Transitions between states can be constrained by guards—conditions that compare clock values to integers—enabling or disabling transitions based on timing conditions. Clocks can also be reset during transitions. Timed automata are a <a href="/facts/Decidable_(logic)/17SHPMo0">decidable</a> subclass of <a href="/facts/Hybrid_automaton/Pp6yDUCQ">hybrid automata</a>, making them theoretically <a href="/facts/Tractable_problem/etHuVF3U">tractable</a> while maintaining significant modeling power. </p><p>Timed automata have become fundamental tools for analyzing time-dependent systems, including real-time systems, communication protocols, and embedded systems. Over the past three decades, researchers have developed methods for verifying both safety properties (ensuring bad states are never reached) and liveness properties (ensuring good states are eventually reached). </p><p>The proof that the state <a href="/facts/Reachability_problem/jlBpsn98">reachability problem</a> for timed automata is <a href="/facts/Decision_problem/cQNWjbdE">decidable</a> was a breakthrough result that spurred extensive research into various extensions, including <a href="/facts/Stopwatch/MpK39IG9">stopwatches</a>, real-time tasks, cost functions, and timed games. Several software tools have been developed to specify and analyze timed automata, with <a href="/facts/Uppaal_Model_Checker/6R4VmIpp">UPPAAL</a>, Kronos, and the TIMES schedulability analyzer being notable examples. While these tools continue to mature, they remain primarily academic research instruments. </p>