Complementation of Rational Sets 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 for finite, infinite, bi-finite and even transfinite words studied by Buchi Kleene's theorem has been generalized to these words. We prove that rational sets of words on countable scattered linear ordering are closed under complementation using an algebraic approach.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00620119
Contributor : Chloé Rispal <>
Submitted on : Monday, October 3, 2011 - 3:25:39 PM
Last modification on : Friday, February 8, 2019 - 3:38:03 PM
Long-term archiving on : Wednesday, January 4, 2012 - 2:26:23 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620119, version 1

Citation

Chloé Rispal, Olivier Carton. Complementation of Rational Sets on Scattered Linear Orderings. 8th International Conference on Developments in Language Theory (DLT 2004), 2004, France. pp.381-392. ⟨hal-00620119⟩

Share

Metrics

Record views

242

Files downloads

106