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, April 12, 2019 - 10:18:03 AM
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

262

Files downloads

133