Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Special issue dedicated to the 14th "Journées montoises d'informatique théorique" ; ; et al in RAIRO : Informatique Théorique et Applications = Theoretical Informatics and Applications (2014), 48 Detailed reference viewed: 12 (1 ULg)Special issue dedicated to the twelfth "Journées montoises d'informatique théorique" ; Rigo, Michel in RAIRO : Informatique Théorique et Applications = Theoretical Informatics and Applications (2010), 44(1), 1-192 Detailed reference viewed: 17 (3 ULg)Special issue dedicated to the second "AutoMathA conference" ; ; et al in Discrete Mathematics & Theoretical Computer Science (2010), 12 Detailed reference viewed: 10 (0 ULg)On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases Boigelot, Bernard ; Brusten, Julien ; in Logical Methods in Computer Science (2010), 6(1), 1-17 This article 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 ... [more ▼] This article 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. This result extends Cobham's theorem, which characterizes the sets of integer numbers that are recognizable by finite automata in multiple bases. In this article, 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 the first order additive theory of real and integer numbers. 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. [less ▲] Detailed reference viewed: 60 (19 ULg)On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases Boigelot, Bernard ; Brusten, Julien ; in Lecture Notes in Computer Science (2008, July), 5126 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 102 (33 ULg)special issue dedicated to the tenth ``Journées montoises d'informatique théorique'' ; Rigo, Michel in Discrete Mathematics & Theoretical Computer Science (2007), 9(2), 1 Detailed reference viewed: 18 (5 ULg) |
||