Accessibility in automata on scattered linear orderings

Olivier Carton (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

In a preceding paper, automata have been introduced for words indexed by linear orderings. These automata are a generalization of automata on transfinite words introduced by Bilchi. In this paper, we show that if only words indexed by scattered linear orderings are considered, the accessibility and the emptiness in these automata can be checked in time nm(2) where n and m are the number of states and the number of transitions. This solves the problem for automata on transfinite words.

Domaines: Automatique

Olivier Carton. Accessibility in automata on scattered linear orderings. MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2002, 2002, 2420 (?), pp.155--164. ⟨hal-00693661⟩