Complementation of Rational Sets on Scattered Linear Orderings of Finite Rank - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2004

Complementation of Rational Sets on Scattered Linear Orderings of Finite Rank

Résumé

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.
Fichier principal
Vignette du fichier
hal.pdf (203.71 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00619905 , version 1 (03-10-2011)

Identifiants

  • HAL Id : hal-00619905 , version 1

Citer

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⟩
141 Consultations
218 Téléchargements

Partager

Gmail Facebook X LinkedIn More