Skip to Main content Skip to Navigation
Journal articles

Complementation of Rational sets on Scattered Linear Orderings of Finite Rank

Abstract : In a preceding paper [1], automata have been introduced for words indexed by linear orderings. These automata are a generalization of automata for finite, infinite, bi-infinite, 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 :
Journal articles
Complete list of metadata

https://hal-upec-upem.archives-ouvertes.fr/hal-00619538
Contributor : Chloé Rispal Connect in order to contact the contributor
Submitted on : Thursday, October 6, 2011 - 2:33:12 PM
Last modification on : Wednesday, October 27, 2021 - 2:38:53 PM
Long-term archiving on: : Saturday, January 7, 2012 - 2:20:22 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

`

Citation

Olivier Carton, Chloé Rispal. Complementation of Rational sets on Scattered Linear Orderings of Finite Rank. Theoretical Computer Science, Elsevier, 2007, 382 (2), pp.109-119. ⟨10.1016/j.tcs.2007.03.008⟩. ⟨hal-00619538⟩

Share

Metrics

Record views

475

Files downloads

729