Search

Your search keyword '"Hoyrup, Mathieu"' showing total 106 results
Start Over Author "Hoyrup, Mathieu"
106 results on '"Hoyrup, Mathieu"'

103. Rewriting Logic and Probabilities.

Author

Goos, Gerhard, Hartmanis, Juris, van Leeuwen, Jan, Nieuwenhuis, Robert, Bournez, Olivier, and Hoyrup, Mathieu

Abstract

Rewriting Logic has shown to provide a general and elegant framework for unifying a wide variety of models, including concurrency models and deduction systems. In order to extend the modeling capabilities of rule based languages, it is natural to consider that the firing of rules can be subject to some probabilistic laws. Considering rewrite rules subject to probabilities leads to numerous questions about the underlying notions and results. In this paper, we discuss whether there exists a notion of probabilistic rewrite system with an associated notion of probabilistic rewriting logic. [ABSTRACT FROM AUTHOR]

Published
2003
Full Text
View/download PDF

104. Comparing computability in two topologies

Author

DJAMEL EDDINE AMIR, MATHIEU HOYRUP, Designing the Future of Computational Models (MOCQUA), 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), and Hoyrup, Mathieu

Subjects
Philosophy, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], [MATH.MATH-GN]Mathematics [math]/General Topology [math.GN], Logic, [MATH.MATH-LO] Mathematics [math]/Logic [math.LO], [MATH.MATH-GN] Mathematics [math]/General Topology [math.GN]
Abstract

Computable analysis provides ways of representing points in a topological space, and therefore of defining a notion of computable points of the space. In this article, we investigate when two topologies on the same space induce different sets of computable points. We first study a purely topological version of the problem, which is to understand when two topologies are not $\sigma $ -homeomorphic. We obtain a characterization leading to an effective version, and we prove that two topologies satisfying this condition induce different sets of computable points. Along the way, we propose an effective version of the Baire category theorem which captures the construction technique, and enables one to build points satisfying properties that are co-meager with respect to a topology, and are computable with respect to another topology. Finally, we generalize the result to three topologies and give an application to prove that certain sets do not have computable type, which means that they have a homeomorphic copy that is semicomputable but not computable.

Published
2022

105. Randomness and the ergodic decomposition

Author

Mathieu Hoyrup, 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), 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), 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)-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), and Hoyrup, Mathieu

Subjects
Discrete mathematics, Pure mathematics, Mathematics::Dynamical Systems, 010102 general mathematics, Ergodicity, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], [MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS], Ergodic hypothesis, 0102 computer and information sciences, Poincaré recurrence theorem, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.1: Mathematical Logic/F.4.1.0: Computability theory, 16. Peace & justice, Stationary ergodic process, 01 natural sciences, ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.2: Computability theory, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], 010201 computation theory & mathematics, Ergodic theory, Invariant measure, 0101 mathematics, Ergodic process, Randomness, Mathematics
Abstract

International audience; The interaction between algorithmic randomness and ergodic theory is a rich field of investigation. In this paper we study the particular case of the ergodic decomposition. We give several positive partial answers, leaving the general problem open. We shortly illustrate how the effectivity of the ergodic decomposition allows one to easily extend results from the ergodic case to the non-ergodic one (namely Poincaré recurrence theorem). We also show that in some cases the ergodic measures can be computed from the typical realizations of the process.

Published
2011

106. Topological Analysis of Representations

Author

Mathieu Hoyrup, Theoretical adverse computations, and safety (CARTE), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), 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), 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)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria), Designing the Future of Computational Models (MOCQUA), 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), 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)-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), and Hoyrup, Mathieu

Subjects
[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Computer science, Process (engineering), 010102 general mathematics, Open set, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 0102 computer and information sciences, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.1: Mathematical Logic/F.4.1.0: Computability theory, Topology, 01 natural sciences, Computable analysis, Decidability, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], Recursively enumerable language, 010201 computation theory & mathematics, Core (graph theory), [MATH.MATH-LO] Mathematics [math]/Logic [math.LO], 0101 mathematics, Representation (mathematics), Topology (chemistry)
Abstract

International audience; Computable analysis is the theoretical study of the abilities of algorithms to process infinite objects. The algorithms abilities depend on the way these objects are presented to them. We survey recent results on the problem of identifying the properties of objects that are decidable or semidecidable, for several concrete classes of objects and representations of them. Topology is at the core of this study, as the decidable and semidecidable properties are closely related to the open sets induced by the representation.

Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results