Paper published in a journal (Scientific congresses and symposiums)
A Generalization of Cobham's Theorem to Automata over Real Numbers
Boigelot, Bernard; Brusten, Julien
2007In Lecture Notes in Computer Science, 4596, p. 813-824
Peer reviewed
 

Files


Full Text
paper.pdf
Author postprint (208.11 kB)
Download

The original publication is available at www.springerlink.com


All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Automata; Real numbers; Mixed real-integer arithmetic; Cobham's theorem
Abstract :
[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.
Disciplines :
Computer science
Author, co-author :
Boigelot, Bernard  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique
Brusten, Julien ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique
Language :
English
Title :
A Generalization of Cobham's Theorem to Automata over Real Numbers
Publication date :
July 2007
Event name :
34th International Colloquium on Automata, Languages and Programming
Event place :
Wroclaw, Poland
Event date :
July 9-13, 2007
Audience :
International
Journal title :
Lecture Notes in Computer Science
ISSN :
0302-9743
eISSN :
1611-3349
Publisher :
Springer, Berlin Heidelberg, Germany
Volume :
4596
Pages :
813-824
Peer reviewed :
Peer reviewed
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Available on ORBi :
since 18 December 2008

Statistics


Number of views
206 (36 by ULiège)
Number of downloads
157 (14 by ULiège)

Scopus citations®
 
3
Scopus citations®
without self-citations
2
OpenCitations
 
2

Bibliography


Similar publications



Contact ORBi