Publications

2024

• Emmanuel Rauzy, Groups with presentations in EDT0L, arXiv 2402.01601 (2024)

2023

• Brattka, Vasco, On the complexity of learning programs, in: Della Vedova, Gianluca and Dundua, Besik and Lempp, Steffen and Manea, Florin (eds.), Unity of Logic and Computation, vol. 13967 of Lecture Notes in Computer Science, Springer, Cham, 2023, pages 166-177
• Brattka, Vasco, The Discontinuity Problem, Journal of Symbolic Logic 88:3 (2023) 1191-1212
• Brattka, Vasco, On the complexity of computing Gödel numbers, arXiv 2302.04213 (2023)
• Emmanuel Rauzy, A generalization of Markov's approach to the continuity problem for Type 1 computable functions, arXiv 2311.15857 (2023)
• Emmanuel Rauzy, Multi-representation associated to the numbering of a subbasis and formal inclusion relations, arXiv 2311.15861 (2023)
• Emmanuel Rauzy, New definitions in the theory of Type 1 computable topological spaces, arXiv 2311.16340 (2023)

2022

• Brattka, Vasco, Weihrauch complexity and the Hagen school of computable analysis, in: Löwe, Benedikt and Sarikaya, Deniz (eds.), 60 Jahre DVMLG, vol. 48 of Tributes, College Publications, London, 2022, pages 13-44
• Brattka, Vasco and Greenberg, Noam and Kalimullin, Iskander and Soskova, Mariya (eds.), Special issue: Oberwolfach Workshop on Computability Theory 2021, vol. 11 of Computability - The Journal of the Association CiE, IOS Press, 2022
• Hölzl, Rupert and Porter, Christoph P., Degrees of randomized computability, Bulletin of Symbolic Logic 28:1 (2022) 27-70

2021

• Brattka, Vasco, Stashing-Parallelization Pentagons, Logical Methods in Computer Science 17:4 (2021) 20:1-20:29
• Brattka, Vasco, Stashing-Parallelization Pentagons, arXiv 2102.11832 (2021)
• Brattka, Vasco and Gherardi, Guido, Completion of Choice, Annals of Pure and Applied Logic 172:3 (2021) 102914
• Brattka, Vasco and Gherardi, Guido and Pauly, Arno, Weihrauch Complexity in Computable Analysis, in: Brattka, Vasco and Hertling, Peter (eds.), Handbook of Computability and Complexity in Analysis, Theory and Applications of Computability, Springer, Cham, 2021, pages 367-417
• Brattka, Vasco and Greenberg, Noam and Kalimullin, Iskander and Soskova, Mariya, Computability theory, Oberwolfach Reports 18:2 (2021) 1149-1190
• Brattka, Vasco and Hertling, Peter (eds.), Handbook of Computability and Complexity in Analysis, Theory and Applications of Computability, Springer, Cham, 2021
• Emmanuel Rauzy, Computable analysis on the space of marked groups, arXiv 2111.01179 (2021)
• Emmanuel Rauzy, Remarks and problems about algorithmic descriptions of groups, arXiv 2111.01190 (2021)

2020

• Brattka, Vasco, The Discontinuity Problem, arXiv 2012.02143 (2020)
• Brattka, Vasco and Dzhafarov, Damir and Marcone, Alberto and Pauly, Arno (eds.), Special issue: Dagstuhl Seminar on Measuring the Complexity of Computational Content 2018, vol. 9 of Computability - The Journal of the Association CiE, IOS Press, 2020
• Brattka, Vasco and Gherardi, Guido, Weihrauch Goes Brouwerian, The Journal of Symbolic Logic 85:4 (2020) 1614-1653
• Hölzl, Rupert and Merkle, Wolfgang and Miller, Joseph and Stephan, Frank and Yu, Liang, Chaitin's Ω as a Continuous Function, The Journal of Symbolic Logic 85:1 (2020) 486-510

2019

• Brattka, Vasco and Downey, Rod G. and Knight, Julia F. and Lempp, Steffen (eds.), Special issue: Oberwolfach Workshop on Computability Theory 2018, vol. 8 of Computability - The Journal of the Association CiE, IOS Press, 2019
• Brattka, Vasco and Dzhafarov, Damir D. and Marcone, Alberto and Pauly, Arno (eds.), Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis (Dagstuhl Seminar 18361), vol. 8 of Dagstuhl Reports, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2019
• Brattka, Vasco and Gherardi, Guido, Completion of Choice, arXiv 1910.13186 (2019)
• Brattka, Vasco and Le Roux, Stéphane and Miller, Joseph S. and Pauly, Arno, Connected Choice and the Brouwer Fixed Point Theorem, Journal of Mathematical Logic 19:1 (2019) 1-46
• Hölzl, Rupert and Porter, Christopher P., Rank and Randomness, The Journal of Symbolic Logic 84:4 (2019) 1527-1543

2018

• Brattka, Vasco, A Galois connection between Turing jumps and limits, Logical Methods in Computer Science 14:3:13 (2018) 1-37
• Brattka, Vasco, A Galois connection between Turing jumps and limits, arXiv 1802.01355 (2018)
• Brattka, Vasco and Downey, Rod and Knight, Julia F. and Lempp, Steffen, Computability theory, Oberwolfach Reports 15:1 (2018) 5-41
• Brattka, Vasco and Gherardi, Guido, Weihrauch Goes Brouwerian, arXiv 1809.00380 (2018)
• Brattka, Vasco and Hendtlass, Matthew and Kreuzer, Alexander P., On the Uniform Computational Content of the Baire Category Theorem, Notre Dame Journal of Formal Logic 59:4 (2018) 605-636
• Brattka, Vasco and Pauly, Arno, On the Algebraic Structure of Weihrauch Degrees, Logical Methods in Computer Science 14:4:4 (2018) 1-36
• Hölzl, Rupert and Jain, Sanjay and Stephan, Frank, Learning pattern languages over groups, Theoretical Computer Science 742 (2018) 66-81

2017

• Bienvenu, Laurent and Hölzl, Rupert and Porter, Christopher P. and Shafer, Paul, Randomness and Semimeasures, Notre Dame Journal of Formal Logic 58:3 (2017) 301-328
• Brattka, Vasco and Cettolo, Andrea and Gherardi, Guido and Marcone, Alberto and Schröder, Matthias, Addendum to: "The Bolzano-Weierstrass Theorem is the Jump of Weak Kőnig's Lemma", Annals of Pure and Applied Logic 168:8 (2017) 1605-1608
• Brattka, Vasco and Cettolo, Andrea and Gherardi, Guido and Marcone, Alberto and Schröder, Matthias, Addendum to: "The Bolzano-Weierstrass Theorem is the Jump of Weak Kőnig's Lemma", arXiv 1101.0792 (2017)
• Brattka, Vasco and Gherardi, Guido and Hölzl, Rupert and Pauly, Arno, The Vitali Covering Theorem in the Weihrauch Lattice, in: Day, Adam and Fellows, Michael and Greenberg, Noam and Khoussainov, Bakhadyr and Melnikov, Alexander and Rosamond, Frances (eds.), Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, vol. 10010 of Lecture Notes in Computer Science, Springer, Cham, 2017, pages 188-200
• Brattka, Vasco and Gherardi, Guido and Pauly, Arno, Weihrauch Complexity in Computable Analysis, arXiv 1707.03202 (2017)
• Brattka, Vasco and Hendtlass, Matthew and Kreuzer, Alexander P., On the Uniform Computational Content of Computability Theory, Theory of Computing Systems 61:4 (2017) 1376-1426
• Brattka, Vasco and Hölzl, Rupert and Kuyper, Rutger, Monte Carlo Computability, in: Vollmer, Heribert and Vallée, Brigitte (eds.), 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), vol. 66 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017, pages 17:1-17:14
• Brattka, Vasco and Rakotoniaina, Tahina, On the Uniform Computational Content of Ramsey's Theorem, Journal of Symbolic Logic 82:4 (2017) 1278-1316
• Hölzl, Rupert and Jain, Sanjay and Schlicht, Philipp and Seidel, Karen and Stephan, Frank, Automatic Learning from Repetitive Texts, in: Hanneke, Steve and Reyzin, Lev (eds.), International Conference on Algorithmic Learning Theory, ALT 2017, 15-17 October 2017, Kyoto University, Kyoto, Japan, vol. 76 of Proceedings of Machine Learning Research, PMLR, 2017, pages 129-150
• Hölzl, Rupert and Jain, Sanjay and Stephan, Frank, Learning pattern languages over groups, Theoretical Computer Science (2017)
• Hölzl, Rupert and Porter, Christopher P., Randomness for computable measures and initial segment complexity, Annals of Pure and Applied Logic 168:4 (2017) 860-886
• Hölzl, Rupert and Raghavan, Dilip and Stephan, Frank and Zhang, Jing, Weakly Represented Families in Reverse Mathematics, in: Day, Adam and Fellows, Michael and Greenberg, Noam and Khoussainov, Bakhadyr and Melnikov, Alexander and Rosamond, Frances (eds.), Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, vol. 10010 of Lecture Notes in Computer Science, Springer, Cham, 2017, pages 160-187
• Schröder, Matthias and Steinberg, Florian, Bounded time computation on metric spaces and Banach spaces, in: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017, pages 1-12

2016

• Brattka, Vasco, Computability and Analysis, a Historical Approach, in: Beckmann, Arnold and Bienvenu, Laurent and Jonoska, Nataša (eds.), Pursuit of the Universal, vol. 9709 of Lecture Notes in Computer Science, Springer, Switzerland, 2016, pages 45-57
• Brattka, Vasco, Computability and Analysis, a Historical Approach, arXiv 1602.07509 (2016)
• Brattka, Vasco and Gherardi, Guido and Hölzl, Rupert and Pauly, Arno, The Vitali Covering Theorem in the Weihrauch Lattice, arXiv 1605.03354 (2016)
• Brattka, Vasco and Kawamura, Akitoshi and Marcone, Alberto and Pauly, Arno (eds.), Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis (Dagstuhl Seminar 15392), vol. 5 of Dagstuhl Reports, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2016
• Brattka, Vasco and Le Roux, Stéphane and Miller, Joseph S. and Pauly, Arno, The Brouwer Fixed Point Theorem Revisited, in: Beckmann, Arnold and Bienvenu, Laurent and Jonoska, Nataša (eds.), Pursuit of the Universal, vol. 9709 of Lecture Notes in Computer Science, Springer, Switzerland, 2016, pages 58-67
• Brattka, Vasco and Le Roux, Stéphane and Miller, Joseph S. and Pauly, Arno, Connected Choice and the Brouwer Fixed Point Theorem, arXiv 1206.4809 (2016)
• Brattka, Vasco and Miller, Joseph S. and Nies, André, Randomness and Differentiability, Transactions of the American Mathematical Society 368:1 (2016) 581-605
• Brattka, Vasco and Pauly, Arno, On the Algebraic Structure of Weihrauch Degrees, arXiv 1604.08348 (2016)
• Hölzl, Rupert and Stephan, Frank and Yu, Liang, On Martin's pointed tree theorem, Computability 5:2 (2016) 147-157
• Hölzl, Rupert and Jain, Sanjay and Stephan, Frank, Inductive inference and reverse mathematics, Annals of Pure and Applied Logic 167:12 (2016) 1242-1266
• Hölzl, Rupert and Jain, Sanjay and Stephan, Frank, Learning Pattern Languages over Groups, in: Algorithmic Learning Theory - 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings, 2016

2015

• Berger, Ulrich and Brattka, Vasco and Selivanov, Victor and Spreen, Dieter and Tsuiki, Hideki (eds.), Computing with Infinite Data: Topological and Logical Foundations Part 1, vol. 25 of Mathematical Structures in Computer Science, Cambridge University Press, Cambridge, 2015
• Berger, Ulrich and Brattka, Vasco and Selivanov, Victor and Spreen, Dieter and Tsuiki, Hideki (eds.), Computing with Infinite Data: Topological and Logical Foundations Part 2, vol. 25 of Mathematical Structures in Computer Science, Cambridge University Press, Cambridge, 2015
• Brattka, Vasco and Gherardi, Guido and Hölzl, Rupert, Las Vegas Computability and Algorithmic Randomness, in: Mayr, Ernst W. and Ollinger, Nicolas (eds.), 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), vol. 30 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2015, pages 130-142
• Brattka, Vasco and Gherardi, Guido and Hölzl, Rupert, Probabilistic Computability and Choice, Information and Computation 242 (2015) 249-286
• Brattka, Vasco and Hendtlass, Matthew and Kreuzer, Alexander P., On the Uniform Computational Content of Computability Theory, arXiv 1501.00433 (2015)
• Brattka, Vasco and Hendtlass, Matthew and Kreuzer, Alexander P., On the Uniform Computational Content of the Baire Category Theorem, arXiv 1510.01913 (2015)
• Brattka, Vasco and Rakotoniaina, Tahina, On the Uniform Computational Content of Ramsey's Theorem, arXiv 1508.00471 (2015)
• Hölzl, Rupert and Shafer, Paul, Universality, optimality, and randomness deficiency, Annals of Pure and Applied Logic 166:10 (2015) 1049-1069
• Hölzl, Rupert and Jain, Sanjay and Stephan, Frank, Inductive Inference and Reverse Mathematics, in: 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, 2015, pages 420-433
• Rakotoniaina, Tahina, On the Computational Strength of Ramsey's Theorem, Ph.D. thesis, Department of Mathematics and Applied Mathematics, University of Cape Town, Rondebosch, South Africa, 2015
• Schröder, Matthias and Selivanov, Victor, Some hierarchies of QCB_0-spaces, Mathematical Structures in Computer Science 25 (2015) 1799-1823

2014

• Avigad, Jeremy and Brattka, Vasco, Computability and analysis: the legacy of Alan Turing, in: Downey, Rod (ed.), Turing's Legacy: Developments from Turing's Ideas in Logic, vol. 42 of Lecture Notes in Logic, Cambridge University Press, Cambridge, UK, 2014, pages 1-47
• Bienvenu, Laurent and Hölzl, Rupert and Miller, Joseph S. and Nies, André, Denjoy, Demuth and density, J. Math. Log. 14:1 (2014) 1450004, 35
• Brattka, Vasco and Diener, Hannes and Spreen, Dieter (eds.), Logic, Computation, Hierarchies, vol. 4 of Ontos Mathematical Logic, Walter de Gruyter, Boston, 2014
• Hölzl, Rupert and Kräling, Thorsten and Stephan, Frank and Wu, Guohua, Initial segment complexities of randomness notions, Information and Computation 234 (2014) 57-67

2013

• Archibald, Margaret and Brattka, Vasco and Escardó, Martín and Hertling, Peter (eds.), Special Issue for the Conference Computability and Complexity in Analysis (CCA 2011), Cape Town, South Africa, January 31-February 4, 2011, Logical Methods in Computer Science, 2013
• Barmpalias, G. and Hölzl, R. and Lewis, A. E. M. and Merkle, W., Analogues of Chaitin's Omega in the computably enumerable sets, Inform. Process. Lett. 113:5-6 (2013) 171-178
• Bonizzoni, Paola and Brattka, Vasco and Löwe, Benedikt (eds.), The Nature of Computation: Logic, Algorithms, Applications, 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013, Proceedings, vol. 7921 of Lecture Notes in Computer Science, Springer, Berlin, 2013
• Brattka, Vasco and Gherardi, Guido and Hölzl, Rupert, Probabilistic Computability and Choice, arXiv 1312.7305 (2013)
• Hölzl, Rupert and Kräling, Thorsten and Merkle, Wolfgang, Time-bounded Kolmogorov complexity and Solovay functions, Theory Comput. Syst. 52:1 (2013) 80-94

2012

• Avigad, Jeremy and Brattka, Vasco, Computability and analysis: the legacy of Alan Turing, arXiv 1206.3431 (2012)
• Avigad, Jeremy and Brattka, Vasco, Computability and analysis: the legacy of Alan Turing, technical report, Isaac Newton Institute for Mathematical Sciences, Cambridge, UK, 2012
• Berger, Ulrich and Brattka, Vasco and Morozov, Andrei S. and Spreen, Dieter (eds.), Continuity, Computability, Constructivity: From Logic to Algorithms, vol. 163 of Annals of Pure and Applied Logic, Elsevier, Amsterdam, 2012
• Brattka, Vasco and Gherardi, Guido and Marcone, Alberto, The Bolzano-Weierstrass Theorem is the Jump of Weak Kőnig's Lemma, Annals of Pure and Applied Logic 163 (2012) 623-655
• Brattka, Vasco and Le Roux, Stéphane and Pauly, Arno, On the Computational Content of the Brouwer Fixed Point Theorem, in: Cooper, S. Barry and Dawar, Anuj and Löwe, Benedikt (eds.), How the World Computes, vol. 7318 of Lecture Notes in Computer Science, Springer, Berlin, 2012, pages 57-67
• Brattka, Vasco and Le Roux, Stéphane and Pauly, Arno, Connected Choice and the Brouwer Fixed Point Theorem, arXiv 1206.4809 (2012)
• Brattka, Vasco and Le Roux, Stéphane and Pauly, Arno, Connected Choice and the Brouwer Fixed Point Theorem, technical report, Isaac Newton Institute for Mathematical Sciences, Cambridge, UK, 2012