Search

Your search keyword '"Olivier Bournez"' showing total 153 results
Start Over Author "Olivier Bournez"
153 results on '"Olivier Bournez"'

151. How to Tackle Integer Weighted Automata Positivity

Author

Yohan Boichut, Pierre-Cyrille Héam, Olga Kouchnarenko, Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges, Combination of approaches to the security of infinite states systems (CASSIS), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Spécification et Vérification [Cachan] (LSV), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS), Olivier Bournez and Igor Potapov, ANR-06-SETI-0014,RAVAJ,Réécriture et Approximation pour la Vérification d'Applications Java(2006), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS)-Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)

Subjects
Theoretical computer science, Computer science, Reachability problem, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], 01 natural sciences, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Graph, Automaton, 010201 computation theory & mathematics, Reachability, 0202 electrical engineering, electronic engineering, information engineering, Tree automaton, Equivalence class, Computer Science::Formal Languages and Automata Theory, The original publication is available at www.springerlink.com, Integer (computer science)
Abstract

International audience; This paper is dedicated to candidate abstractions to capture relevant aspects of the integer weighted automata. The expected effect of applying these abstractions is studied to build the deterministic reachability graphs allowing us to semi-decide the positivity problem on these automata. Moreover, the papers reports on the implementations and experimental results, and discusses other encodings.

Published
2009
Full Text
View/download PDF

152. A Reduction Theorem for the Verification of Round-Based Distributed Algorithms

Author

Stephan Merz, Mouna Chaouch-Saad, Bernadette Charron-Bost, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Proof-oriented development of computer-based systems (MOSEL), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Olivier Bournez and Igor Potapov, CMCU Defi Utique Tunisie, and École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Consensus algorithm, Theoretical computer science, Computer science, ACM: D.: Software/D.1: PROGRAMMING TECHNIQUES/D.1.3: Concurrent Programming/D.1.3.0: Distributed programming, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.1: Mathematical Logic/F.4.1.10: Temporal logic, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Reduction (complexity), distributed computing, Consensus, 0202 electrical engineering, electronic engineering, information engineering, formal verification, Formal verification, Standard model (cryptography), [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Local property, 020207 software engineering, Fault tolerance, Heard-Of model, ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.1: Specifying and Verifying and Reasoning about Programs, 16. Peace & justice, fault-tolerance, ACM: D.: Software/D.2: SOFTWARE ENGINEERING/D.2.4: Software/Program Verification/D.2.4.4: Model checking, 010201 computation theory & mathematics, Distributed algorithm
Abstract

International audience; We consider the verification of algorithms expressed in the Heard-Of Model, a round-based computational model for fault-tolerant distributed computing. Rounds in this model are communication-closed, and we show that every execution recording individual events corresponds to a coarser-grained execution based on global rounds such that the local views of all processes are identical in the two executions. This result helps us to substantially mitigate state-space explosion and verify Consensus algorithms using standard model checking techniques.

Published
2009
Full Text
View/download PDF

153. Modèles de calcul sur les réels, résultats de comparaison

Author

Hainry, Emmanuel, Theoretical adverse computations, and safety (CARTE), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Institut National Polytechnique de Lorraine - INPL, Jean-Yves Marion(Jean-Yves.Marion@loria.fr), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Institut National Polytechnique de Lorraine, Jean-Yves Marion, and Olivier Bournez

Subjects
General Purpose Computer, elementary functions, hiérarchie de Grzegorczyk, analog computation, Analyse récursive, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Grzgorczyk hierarchy, Hiérarchie de Grzgorczyk, calculabilité réelle, Recursive analysis, Grzegorczyk hierarchy, General Purpose Analog Computer, fonctions élémentaires
Abstract

Computation on the real numbers can be modelised in several different ways.There indeed exist a lot of different computation models on the reals.However, there exist few results for comparing those models, and most of theseresults are incomparability results. The case of computation over the realnumbers hence is quite different from that of computation over integer numberswhere Church-Turing's thesis claims that all reasonable models compute exactlythe same functions.The results presented in this document are twofold.One, we show that recursively computable functions (in the sense ofcomputable analysis) can be shown equivalent to some adequately definedsubclass of R-recursive functions, and also to GPAC-computable functionswith GPAC-computable roughly meaning computable through a convergingGPAC. Hence we get a machine independent characterization of recursivelycomputable functions, and a bridge between type 2-machines and GPAC.Two, more than an analog characterization of recursively enumerablefunctions, we show that the limit operator we defined can be used to providean analog characterization of elementarily computable functions andEn-computable functions for n?3, where Enrepresents the levels of Grzegorczyk's hierarchy.Those results can be seen as a first step toward a unification of computablefunctions over the reals.; Il existe de nombreux modèles de calcul sur les réels. Ces différents modèlescalculent diverses fonctions, certains sont plus puissants que d'autres,certains sont deux à deux incomparables. Le calcul sur les réels est donc dece point de vue bien différent du calcul sur les entiers qui est unifié par lathèse de Church-Turing qui affirme que tous les modèles raisonnables calculentles mêmes fonctions.Les résultats de cette thèse sont de deux sortes. Premièrement, nousmontrons des équivalences entre les fonctions récursivement calculables et unecertaine classe de fonctions R-récursives et entre les fonctionsGPAC-calculables et les fonctions récursivement calculables. Ces deuxrésultats ne sont cependant valables que si les fonctions présentent quelquescaractéristiques : elles doivent être définies sur un compact et dans lepremier cas être de classe C^2. Deuxièmement, nous montrons également unehiérarchie de classes de fonctions R-récursives qui caractérisent lesfonctions élémentairement calculables, les fonctionsEn-calculables pour n?3 (où les En sont lesfonctions de la hiérarchie de Grzegorczyk), et des fonctions récursivementcalculables. Ce résultat utilise un opérateur de limite dont nous avons prouvéla généralité en montrant qu'il transfère une inclusion sur la partie discrètedes fonctions en une inclusion sur les fonctions sur les réels elles-mêmes.Ces résultats constituent donc une avancée vers une éventuelleunification des modèles de calcul sur les réels.

Published
2006

Catalog

Books, media, physical & digital resources
See catalog results