Complementation of Rational Sets on Scattered Linear Orderings of Finite Rank

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 show that deterministic automata do not have the same expressive power. Despite this negative result, we prove that rational sets of words of finite ranks are closed under complementation.
Document type :
Conference papers
Complete list of metadatas

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

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619905, version 1

Citation

Olivier Carton, Chloé Rispal. Complementation of Rational Sets on Scattered Linear Orderings of Finite Rank. 6th Latin American Theoretical INformatics (LATIN'04), Apr 2004, Buenos Aires, Argentina, Argentina. pp.292-301. ⟨hal-00619905⟩

Share

Metrics

Record views

319

Files downloads

186