Skip to Main content Skip to Navigation
Journal articles

Accessibility in automata on scattered linear orderings

Abstract : 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Olivier Carton Connect in order to contact the contributor
Submitted on : Wednesday, May 2, 2012 - 10:02:17 PM
Last modification on : Saturday, January 15, 2022 - 3:56:01 AM


  • HAL Id : hal-00693661, version 1



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



Record views