Automata on infinite linear orders

Slides

In this talk, we present automata accepting words indexed by linear ordering. These automata are simple but they generalize automata on finite words, infinite words, bi-infinite words, and transfinite words.

The set words accepted by these automata can also be described by regular expressions (Kleene like theorem), including the usual regular expressions for finite words.

We also mention the complementation problem and the links to logic.

This document was translated from L^AT_EX by H^EV^EA.