How can a machine accept an infinite input?

Acceptance is defined not by reaching a final state at the end, since there is no end, but by which states recur. A Büchi automaton, for example, accepts when it passes through a designated accepting state infinitely often during its endless run.

Why are these automata important for verification?

Non-terminating systems such as operating systems and network protocols are naturally modeled by infinite behaviors. Properties like "the system never deadlocks" or "every request is eventually served" become omega-regular languages, so checking them reduces to automata operations that a model checker can perform automatically.

Automata on Infinite Objects

Automata on infinite objects read inputs that never end, such as infinite words or infinite trees, and accept according to which states or transitions are visited infinitely often, providing the mathematical machinery for reasoning about ongoing, non-terminating systems.

Definition

An omega-automaton is a finite-state machine whose runs are infinite, with acceptance defined by a condition on the set of states visited infinitely often; such automata recognize sets of infinite words or trees called omega-regular languages.

Scope

This topic covers Büchi, Muller, Rabin, and parity automata over infinite words, the acceptance conditions that distinguish them, determinization and complementation results, automata over infinite trees, and the deep connections between these automata, monadic second-order logic, and infinite games used in synthesis and verification.

Core questions

How can a finite machine accept or reject an input that has no end?
Why do nondeterministic and deterministic Büchi automata differ in expressive power?
How do automata over infinite objects relate to logics for specifying system behavior?
What makes complementation of these automata difficult, and why does it matter?

Key theories

Büchi acceptance and omega-regular languages: A Büchi automaton accepts an infinite word when some accepting state is visited infinitely often, and the languages so recognized, the omega-regular languages, coincide with those definable in monadic second-order logic over the natural numbers.
Determinization and the parity condition: Nondeterministic Büchi automata cannot in general be made deterministic without changing the acceptance condition, but Safra's construction converts them to deterministic Rabin or parity automata, which is essential for complementation and for solving games.

Clinical relevance

Omega-automata are the algorithmic backbone of model checking: a reactive system and a temporal-logic property are each translated into automata over infinite words, and checking the property reduces to an emptiness test, enabling automated verification of hardware, protocols, and concurrent software.

History

Büchi introduced automata on infinite words around 1960 to decide the monadic second-order theory of the natural numbers, McNaughton showed how to determinize them with stronger acceptance conditions, and Rabin extended the theory to infinite trees, results that became central to verification after temporal logic entered computer science in the late 1970s.

Key figures

J. Richard Büchi
Robert McNaughton
Michael Rabin
Shmuel Safra

Seminal works

thomas1990
graedel2002

Frequently asked questions

How can a machine accept an infinite input?: Acceptance is defined not by reaching a final state at the end, since there is no end, but by which states recur. A Büchi automaton, for example, accepts when it passes through a designated accepting state infinitely often during its endless run.
Why are these automata important for verification?: Non-terminating systems such as operating systems and network protocols are naturally modeled by infinite behaviors. Properties like "the system never deadlocks" or "every request is eventually served" become omega-regular languages, so checking them reduces to automata operations that a model checker can perform automatically.