Université de Liège Réseau des Bibliothèques

BICTEL/e - ULg
Serveur institutionnel des thèses de doctorat



Nouvelles thèses
dans BICTEL/e - ULg
  • Stiepen, Arnaud - Dynamics and compisition of Mars and Venus upper atmospheres observed by the ultraviolet spectrographs on board Mars Express and Venus Express/ Dynamique et composition des atmosphères supérieures de Mars et Vénus observées par les spectrographes ultraviolets à bord de Mars Express et Vénus Express
  • Collignon, Amandine - Abondance et variabilité des méduses en Baie de Calvi (Corse)
  • Hermans, Thomas - Integration of near-surface geophysical, geological and hydrogeological data with multiple-point geostatistics in alluvial aquifers
Présentation Recherche thèse Dépôt thèse Accès
gestionnaires
 
Page de résumé pour ULgetd-03312011-135259

Auteur : Brusten, Julien
E-mail de l'auteur : Julien.Brusten@ulg.ac.be
URN : ULgetd-03312011-135259
Langue : Français/French
Titre : On the sets of real vectors recognized by finite automata in multiple bases
Intitulé du diplôme : Doctorat en sciences (orientation informatique)
Département : FSA - Département d'électricité, électronique et informatique
Jury :
Nom : Titre :
Bruyere, Véronique Membre du jury/Committee Member
Durand, Fabien Membre du jury/Committee Member
Leroux, Jérôme Membre du jury/Committee Member
Rigo, Michel Membre du jury/Committee Member
Wolper, Pierre Membre du jury/Committee Member
Gribomont, Pascal Président du jury/Committee Chair
Boigelot, Bernard Promoteur/Director
Mots-clés :
  • symbolic representation/représentation symbolique
  • recognizability in multiple bases/reconnaissance dans des bases multiples
  • Cobham's theorem/théorème de Cobham
  • real vectors/vecteurs de réels
  • Semenov's theorem/théorème de Semenov
  • mixed real-integer arithmetic/arithmétique des entiers et des réels
  • finite automata/automates finis
Date de soutenance : 2011-06-08
Type d'accès : Public/Internet
Résumé :

This thesis studies the properties of finite automata recognizing sets of real vectors encoded in positional notation using an integer base. We consider both general infinite-word automata, and the restricted class of weak deterministic automata, used, in particular, as symbolic data structures for representing the sets of vectors definable in the first order additive theory of real and integer numbers.



In previous work, it has been established that all sets definable in the additive theory of reals and integers can be handled by weak deterministic automata regardless of the chosen numeration base. In this thesis, we address the reciprocal property, proving that the sets of vectors that are simultaneously recognizable in all bases, by either weak deterministic or Muller automata, are those definable in the additive theory of reals and integers.



Precisely, for weak deterministic automata, we establish that the sets of real vectors simultaneously recognizable in two multiplicatively independent bases are necessarily definable in the additive theory of reals and integers. For general automata, we show that the multiplicative independence is not sufficient, and we prove that, in this context, the sets of real vectors that

are recognizable in two bases that do not share the same set of prime factors are exactly those definable in the additive theory of reals and integers.



Those results lead to a precise characterization of the sets of real vectors that are recognizable in multiple bases, and provide a theoretical justification to the use of weak automata as symbolic representations of sets.



As additional contribution, we also obtain valuable insight into the internal structure of automata recognizing sets of vectors definable in the additive theory of reals and integers.

Autre version :
Fichiers :
Nom du fichier Taille Temps de chargement évalué (HH:MI:SS)
Modem 56K ADSL
[Public/Internet] thesis.pdf 1.01 Mb 00:02:23 00:00:05

Bien que le maximum ait été fait pour que les droits des ayants-droits soient respectés, si un de ceux-ci constatait qu'une oeuvre sur laquelle il a des droits a été utilisée dans BICTEL/e ULg sans son autorisation explicite, il est invité à prendre contact le plus rapidement possible avec la Direction du Réseau des Bibliothèques.


Parcourir BICTEL/e par Auteur|Département | Rechercher dans BICTEL/e


© Réseau des Bibliothèques de l'ULg, Grande traverse, 12 B37 4000 LIEGE