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 metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00619538
Contributor : Chloé Rispal <>
Submitted on : Thursday, October 6, 2011 - 2:33:12 PM
Last modification on : Friday, March 27, 2020 - 3:07:01 AM
Document(s) archivé(s) le : 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

388

Files downloads

476