Reference : On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases
Scientific congresses and symposiums : Paper published in a journal
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/2792
On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases
English
Boigelot, Bernard mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique >]
Brusten, Julien mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique >]
Bruyère, Véronique mailto [Université de Mons-Hainaut - UMH > Institut d'Informatique > > >]
Jul-2008
Lecture Notes in Computer Science
Springer
5126
112-123
Yes
No
International
0302-9743
1611-3349
Berlin Heidelberg
Germany
35th International Colloquium on Automata, Languages and Programming
July 7-11, 2008
Reykjavik
Iceland
[en] Automata ; Real numbers ; Mixed real-integer arithmetic ; Cobham's theorem
[en] This paper studies the expressive power of finite automata recognizing sets of real numbers encoded in positional notation. We consider Muller automata as well as the restricted class of weak deterministic automata, used as symbolic set representations in actual applications. In previous work, it has been established that the sets of numbers that are recognizable by weak deterministic automata in two bases that do not share the same set of prime factors are exactly those that are definable in the first order additive theory of real and integer numbers (R, Z, +, <). This result extends Cobham's theorem, which characterizes the sets of integer numbers that are recognizable by finite automata in multiple bases.

In this paper, we first generalize this result to multiplicatively independent bases, which brings it closer to the
original statement of Cobham's theorem. Then, we study the sets of reals recognizable by Muller automata in two bases. We show with a counterexample that, in this setting, Cobham's theorem does not generalize to multiplicatively independent bases. Finally, we prove that the sets of reals that are recognizable by Muller automata in two bases that do not share the same set of prime factors are exactly those definable in (R, Z, +, <). These sets are thus also recognizable by weak deterministic automata. This result leads to a precise characterization of the sets of real numbers that are recognizable in multiple bases, and provides a theoretical justification to the use of weak automata as symbolic representations of sets.
Fonds de la Recherche Scientifique (Communauté française de Belgique) - F.R.S.-FNRS ; Interuniversity Attraction Poles program MoVES of the Belgian Federal Science Office ; Grant 2.4530.02 of the Belgian Fund for Scientific Research (F.R.S.-FNRS)
http://hdl.handle.net/2268/2792
10.1007/978-3-540-70583-3_10
http://www.springerlink.com/content/4887045600025u72/
The original publication is available at www.springerlink.com

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
BoigelotNumbers.pdfAuthor postprint203.33 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.