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 metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00693661
Contributor : Olivier Carton <>
Submitted on : Wednesday, May 2, 2012 - 10:02:17 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:03 PM

Identifiers

  • HAL Id : hal-00693661, version 1

Collections

Citation

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

Share

Metrics

Record views

210