Ongoing or submitted work

• Local generation of tilings.
  Tom Favereau and Mathieu Hoyrup.
  [pdf, arXiv]
• Local generation of tilings: the even bicolor Wang tilesets.
  Tom Favereau and Mathieu Hoyrup.
  [pdf, arXiv]
• Descriptive complexity of topological invariants.
  Djamel Eddine Amir and Mathieu Hoyrup.
  [pdf, HAL]

Published

2024

• The surjection property and computable type.
  Djamel Eddine Amir and Mathieu Hoyrup.
  Topology and its Applications [pdf, arXiv, HAL, doi]

2023

• Degree spectra of homeomorphism types of compact Polish spaces.
  Mathieu Hoyrup, Takayuki Kihara and Victor Selivanov.
  Journal of Symbolic Logic [pdf, arXiv, HAL, doi]
• Notes on overt choice.
  Mathieu Hoyrup.
  Computability 12(4):351-369 [pdf, HAL, doi]
• Strong computable type.
  Djamel Eddine Amir and Mathieu Hoyrup.
  Computability 12(3):227-269 [pdf, arXiv, HAL, doi]
• Comparing computability in two topologies.
  Djamel Eddine Amir and Mathieu Hoyrup.
  Journal of Symbolic Logic 89(3):1232-1250 [pdf, HAL, doi]

2022

• Realizing semicomputable simplices by computable dynamical systems.
  Daniel Coronel, Alexander Frank, Mathieu Hoyrup and Cristóbal Rojas.
  Theoretical Computer Science 933:43-54 [pdf, HAL, doi]
• Computability of finite simplicial complexes.
  Djamel Eddine Amir and Mathieu Hoyrup.
  ICALP 2022. [pdf, HAL, doi]
• The fixed-point property for represented spaces.
  Mathieu Hoyrup.
  Annals of Pure and Applied Logic 173(5). [pdf, HAL, doi]

2020

• Descriptive complexity on non-Polish spaces II.
  Mathieu Hoyrup.
  ICALP 2020. [pdf, HAL, doi]
• Descriptive complexity on non-Polish spaces.
  Antonin Callard and Mathieu Hoyrup.
  STACS 2020. [pdf, HAL, doi]

2019

• Semicomputable points in Euclidean spaces.
  Mathieu Hoyrup and Donald M. Stull.
  MFCS 2019. [pdf, doi]
• Computability on quasi-Polish spaces.
  Mathieu Hoyrup, Cristóbal Rojas, Victor Selivanov and Donald M. Stull.
  DCFS 2019. [pdf, doi]

2018

• Semicomputable geometry.
  Mathieu Hoyrup, Diego Nava Saucedo and Donald M. Stull.
  ICALP 2018. [pdf, doi, HAL]

2017

• On the extension of computable real functions.
  Mathieu Hoyrup and Walid Gomaa.
  LICS 2017. [pdf, doi]
• Genericity of weakly computable objects.
  Mathieu Hoyrup.
  Theory of Computing Systems, 60(3):396-420 [doi, pdf, HAL]
• On the information carried by programs about the objects they compute.
  Mathieu Hoyrup and Cristóbal Rojas.
  Theory of Computing Systems, 61(4):1214-1236 [doi]
• Layerwise computability and image randomness.
  Laurent Bienvenu, Mathieu Hoyrup and Alexander Shen.
  Theory of Computing Systems, 61(4):1353-1375 [doi]

2016

• The decidable properties of subrecursive functions.
  Mathieu Hoyrup.
  ICALP 2016. [doi, pdf, HAL]
• The typical constructible object.
  Mathieu Hoyrup.
  CiE 2016. LNCS, 9709:115-123, 2016 [doi, slides]

2015

• Characterizing polynomial time complexity of stream programs using interpretations.
  Hugo Férée, Emmanuel Hainry, Mathieu Hoyrup and Romain Péchoux.
  Theoretical Computer Science, 585:41-54, 2015 [doi]
• On the information carried by programs about the objects they compute.
  Mathieu Hoyrup and Cristóbal Rojas.
  STACS 2015. [pdf, HAL, arXiv, doi]
• Immune Systems in Computer Virology.
  Guillaume Bonfante, Mohamed El-Aqqad, Benjamin Greenbaum, Mathieu Hoyrup.
  CiE 2015. LNCS, 9136:127-136, 2015 [doi]

2014

• Analytical properties of resource-bounded real functionals.
  Hugo Férée, Walid Gomaa, Mathieu Hoyrup.
  Journal of Complexity, 30(5):647-671, 2014 [pdf, doi]
• Irreversible computable functions.
  Mathieu Hoyrup.
  STACS 2014. [pdf, doi]

2013

• Computability of the ergodic decomposition.
  Mathieu Hoyrup.
  Annals of Pure and Applied Logic,164(5):542-549, 2013 [pdf, HAL, doi]
• On the query complexity of real functionals.
  Hugo Férée, Walid Gomaa and Mathieu Hoyrup.
  LICS 2013. [pdf, HAL, doi]

2012

• Computability of the Radon-Nikodym derivative.
  Mathieu Hoyrup, Cristóbal Rojas and Klaus Weihrauch.
  Computability, 1:1-11, 2012 [doi]
• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points.
  Laurent Bienvenu, Adam Day, Mathieu Hoyrup, Ilya Mezhirov and Alexander Shen.
  Information and Computation, 210:21-30, 2012 [pdf, arXiv, doi]
• The dimension of ergodic random sequences.
  Mathieu Hoyrup.
  STACS 2012. [pdf, HAL, arXiv, doi]

2011

• Algorithmic tests and randomness with respect to a class of measures.
  Laurent Bienvenu, Peter Gács, Mathieu Hoyrup, Cristóbal Rojas and Alexander Shen.
  Proceedings of the Steklov Institute of Mathematics (Trudy Miran), 274(1):34-89 [pdf, pdf in Russian, arXiv, doi]
• Dynamics and abstract computability: computing invariant measures.
  Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas.
  Discrete and Continuous Dynamical Systems - Series A, 29(1):193-212, January 2011 [pdf, HAL, doi]
• Randomness on Computable Probability Spaces-A Dynamical Point of View.
  Peter Gács, Mathieu Hoyrup and Cristóbal Rojas.
  Theory of Computing Systems, 48(3):465-485, 2011 [doi]
• Computability of the Radon-Nikodym derivative.
  Mathieu Hoyrup, Cristóbal Rojas and Klaus Weihrauch.
  CiE 2011. LNCS, 6735:132-141, 2011 [pdf, doi, HAL]
• Randomness and the ergodic decomposition.
  Mathieu Hoyrup.
  CiE 2011. LNCS, 6735:122-131, 2011 [pdf, doi, HAL, arXiv]

2010

• Effective symbolic dynamics, random points, statistical behavior, complexity and entropy.
  Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas.
  Information and Computation, 208(1):23-41, 2010 [pdf, arXiv, HAL, doi]
• Interpretation of stream programs: characterizing type 2 polynomial time complexity.
  Hugo Férée, Emmanuel Hainry, Mathieu Hoyrup and Romain Péchoux.
  ISAAC 2010. LNCS, 6506:291-303, 2010 [pdf, doi, HAL]

2009

• A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties.
  Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas.
  Theoretical Computer Science, 410(21-23):2207-2222, 2009 [pdf, arXiv, doi]
• Computability of probability measures and Martin-Löf randomness over metric spaces.
  Mathieu Hoyrup and Cristóbal Rojas.
  Information and Computation, 207(7):830-847, 2009 [pdf, arXiv, doi]
• An application of Martin-Löf randomness to effective probability theory.
  Mathieu Hoyrup and Cristóbal Rojas.
  CiE 2009. LNCS, 5635:260-269, 2009 [pdf, doi]
• Applications of effective probability theory to Martin-Löf randomness.
  Mathieu Hoyrup and Cristóbal Rojas.
  ICALP 2009. LNCS, 5555:549-561, 2009 [pdf, doi]
• Randomness on computable probability spaces - a dynamical point of view.
  Peter Gács, Mathieu Hoyrup and Cristóbal Rojas.
  STACS 2009 [pdf, arXiv, HAL, DROPS]

2008

• Computability and the morphological complexity of some dynamics on continuous domains.
  Mathieu Hoyrup, Arda Kolçak and Giuseppe Longo.
  Theoretical Computer Science, 398(1-3):170-182, 2008 [doi]

2007

• Dynamical systems: stability and simulability.
  Mathieu Hoyrup.
  Mathematical Structures in Computer Science, 17(2):247-259, 2007 [doi]

2003

• Rewriting logic and probabilities.
  Olivier Bournez and Mathieu Hoyrup.
  RTA 2003. LNCS, 2706:61-75, 2003 [pdf, doi]

Surveys

• Algorithmic randomness and layerwise computability.
  Mathieu Hoyrup.
  Algorithmic Randomness: Progress and Prospects, Lecture Notes in Logic, Cambridge University Press 2020.
• Computable Measure Theory and Algorithmic Randomness.
  Mathieu Hoyrup, Jason Rute.
  Chapter in Handbook of Computability and Complexity in Analysis, Springer, 2021. [HAL]
• Statistical properties of dynamical systems - simulation and abstract computation.
  Stefano Galatolo, Mathieu Hoyrup, Cristóbal Rojas.
  Chaos, Solitons and Fractals, 45(1):1-14, 2012. [HAL, doi]
• Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems.
  Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas.
  Proceedings of CCA 2010. [arXiv, HAL]
• Une brève introduction à la théorie effective de l'aléatoire.
  Laurent Bienvenu, Mathieu Hoyrup.
  Gazette des mathématiciens, 123:35-47, 2010 [pdf (in french), link, HAL]

Other works

• Computability of invariant measures: two counter-examples .
  Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas. [pdf]
• Absolute continuity of measures and preservation of randomness.
  Mathieu Hoyrup and Cristóbal Rojas. [pdf]

Thesis

• Computability, Randomness and Ergodic Theory on Metric Spaces.
  PhD thesis, Université Paris Diderot (Paris VII), 2008.
  
  • electronic version (with hyperlinks) [pdf]
  • printable version (without hyperlinks, odd pages on the right) [pdf]
  • archive [TEL]
  • french summary [pdf]
  • english summary [pdf]

Habilitation à diriger des recherches

• Topological Aspects of Representations in Computable Analysis. [pdf, HAL]