Room P4.35, Mathematics Building

Alexander Rabinovich, Tel Aviv University, Israel
On Expressive Power of Regular Expressions over Infinite Orders

Two fundamental results of classical automata theory are the Kleene theorem and the Buchi-Elgot-Trakhtenbrot theorem. Kleene's theorem states that a language of finite words is definable by a regular expression iff it is accepted by a finite state automaton. Buchi-Elgot-Trakhtenbrot's theorem states that a language of finite words is accepted by a finite-state automaton iff it is definable in the weak monadic second-order logic.

Hence, the weak monadic logic and regular expressions are expressively equivalent over finite words. We generalize this to words over arbitrary linear orders.