Name
Abstract | ||
|---|---|---|
This article 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 can all be recognized by weak deterministic Buchi automata, regardless of the encoding base r1. In this article, we prove the reciprocal property, i.e., a subset of R that is recognizable by weak deterministic automata in every base r1 is necessarily definable in . 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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.tcs.2008.12.051 | Theoretical Computer Science |
Keywords | Field | DocType |
Automata,finite-state automaton,finite-state recognizability,Real numbers,Mixed real-integer arithmetic,article study,weak deterministic automaton,encoded positionally,real number,efficient data structure,base r1,Cobham’s theorem,weak deterministic Buchi automaton,encoding base r1 | Discrete mathematics,Computer science,Automaton,Real number | Conference |
Volume | Issue | ISSN |
410 | 18 | Theoretical Computer Science |
ISBN | Citations | PageRank |
3-540-73419-8 | 5 | 0.44 |
References | Authors | |
15 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernard Boigelot | 1 | 707 | 48.59 |
| Julien Brusten | 2 | 20 | 2.27 |