Doctoral thesis (Dissertations and theses)
On the sets of real vectors recognized by finite automata in multiple bases
Brusten, Julien
2011
 

Files


Full Text
thesis.pdf
Author preprint (1.01 MB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
représentation symbolique ; reconnaissance dans des bases multiples ; théorème de Cobham ; vecteurs de réels ; théorème de Semenov ; arithmétique des entiers et des réels ; automates finis; symbolic representation ; recognizability in multiple bases ; Cobham's theorem ; real vectors ; Semenov's theorem ; mixed real-integer arithmetic ; finite automata
Abstract :
[en] 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.
Disciplines :
Computer science
Author, co-author :
Brusten, Julien ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique
Language :
English
Title :
On the sets of real vectors recognized by finite automata in multiple bases
Defense date :
08 June 2011
Number of pages :
xii, 172
Institution :
ULiège - Université de Liège
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique
BELSPO - SPP Politique scientifique - Service Public Fédéral de Programmation Politique scientifique
Available on ORBi :
since 31 May 2011

Statistics


Number of views
298 (63 by ULiège)
Number of downloads
304 (40 by ULiège)

Bibliography


Similar publications



Contact ORBi