Reference : A Generalization of Cobham's Theorem to Automata over Real Numbers
Scientific congresses and symposiums : Paper published in a journal
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/2791
A Generalization of Cobham's Theorem to Automata over Real Numbers
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 >]
Jul-2007
Lecture Notes in Computer Science
Springer
4596
813-824
Yes
No
International
0302-9743
1611-3349
Berlin Heidelberg
Germany
34th International Colloquium on Automata, Languages and Programming
July 9-13, 2007
Wroclaw
Poland
[en] Automata ; Real numbers ; Mixed real-integer arithmetic ; Cobham's theorem
[en] This paper studies the expressive power of finite-state automata recognizing sets of real numbers encoded positionally. It is known that the sets that are definable in the first-order additive theory of real and integer variables (R, Z, +, <) can all be recognized by weak deterministic Büchi automata, regardless of the encoding base r > 1. In this paper, we prove the reciprocal property, i.e., that a subset of R that is recognizable by weak deterministic automata in every base r > 1 is necessarily definable in (R, Z, +, <). This result generalizes to real numbers the well-known Cobham's theorem on the finite-state recognizability of sets of integers. Our proof gives interesting insight into the internal structure of automata recognizing sets of real numbers, which may lead to efficient data structures for handling these sets.
Fonds de la Recherche Scientifique (Communauté française de Belgique) - F.R.S.-FNRS
Researchers ; Professionals
http://hdl.handle.net/2268/2791
10.1007/978-3-540-73420-8
http://www.springerlink.com/content/35673n6823532811/
The original publication is available at www.springerlink.com

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
paper.pdfAuthor postprint203.23 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.