Browse ORBi by ORBi project

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

Automata-Based Symbolic Representations of Polyhedra Boigelot, Bernard ; Brusten, Julien ; Degbomont, Jean-François in Lecture Notes in Computer Science (2012, March), 7183 Detailed reference viewed: 66 (23 ULg)On the sets of real vectors recognized by finite automata in multiple bases Brusten, Julien Doctoral thesis (2011) This thesis studies the properties of finite automata recognizing sets of real vectors encoded in positional notation using an integer base. We consider both general infinite-word automata, and the ... [more ▼] This thesis studies the properties of finite automata recognizing sets of real vectors encoded in positional notation using an integer base. We consider both general infinite-word automata, and the restricted class of weak deterministic automata, used, in particular, as symbolic data structures for representing the sets of vectors definable in the first order additive theory of real and integer numbers. In previous work, it has been established that all sets definable in the additive theory of reals and integers can be handled by weak deterministic automata regardless of the chosen numeration base. In this thesis, we address the reciprocal property, proving that the sets of vectors that are simultaneously recognizable in all bases, by either weak deterministic or Muller automata, are those definable in the additive theory of reals and integers. Precisely, for weak deterministic automata, we establish that the sets of real vectors simultaneously recognizable in two multiplicatively independent bases are necessarily definable in the additive theory of reals and integers. For general automata, we show that the multiplicative independence is not sufficient, and we prove that, in this context, the sets of real vectors that are recognizable in two bases that do not share the same set of prime factors are exactly those definable in the additive theory of reals and integers. Those results lead to a precise characterization of the sets of real vectors that are recognizable in multiple bases, and provide a theoretical justification to the use of weak automata as symbolic representations of sets. As additional contribution, we also obtain valuable insight into the internal structure of automata recognizing sets of vectors definable in the additive theory of reals and integers. [less ▲] Detailed reference viewed: 182 (57 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: 58 (19 ULg)Implicit Real Vector Automata Boigelot, Bernard ; Brusten, Julien ; Degbomont, Jean-François in Electronic Proceedings in Theoretical Computer Science [=EPTCS] (2010), 39 This paper addresses the symbolic representation of non-convex real polyhedra, i.e., sets of real vectors satisfying arbitrary Boolean combinations of linear constraints. We develop an original data ... [more ▼] This paper addresses the symbolic representation of non-convex real polyhedra, i.e., sets of real vectors satisfying arbitrary Boolean combinations of linear constraints. We develop an original data structure for representing such sets, based on an implicit and concise encoding of a known structure, the Real Vector Automaton. The resulting formalism provides a canonical representation of polyhedra, is closed under Boolean operators, and admits an efficient decision procedure for testing the membership of a vector. [less ▲] Detailed reference viewed: 103 (41 ULg)A Generalization of Semenov's Theorem to Automata over Real Numbers Boigelot, Bernard ; Brusten, Julien ; in Lecture Notes in Artificial Intelligence (2009), 5663 Detailed reference viewed: 82 (37 ULg)A generalization of Cobham's theorem to automata over real numbers Boigelot, Bernard ; Brusten, Julien in Theoretical Computer Science (2009), 410(18), 1694-1703 Detailed reference viewed: 54 (27 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)A Generalization of Cobham's Theorem to Automata over Real Numbers Boigelot, Bernard ; Brusten, Julien in Lecture Notes in Computer Science (2007, July), 4596 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 140 (33 ULg) |
||