Automata on linear orderings

AbstractWe consider words indexed by linear orderings. These extend finite, (bi-)infinite words and words on ordinals. We introduce finite automata and rational expressions for these words. We prove that for countable scattered linear orderings, these two notions are equivalent. This result extends Kleene's theorem