18 Search Results for "Brattka, Vasco"

Document
DOI: 10.4230/LIPIcs.STACS.2026.61
On Effective Banach-Mazur Games and an Application to the Poincaré Recurrence Theorem for Category

Authors: Prajval Koul and Satyadev Nandakumar

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
The classical Banach-Mazur game characterizes sets of first category in a topological space. In this work, we show that an effectivized version of the game yields a characterization of sets of effective first category. Using this, we provide a game-theoretic proof of an effective theorem in dynamical systems, namely the category version of Poincaré Recurrence. The Poincaré Recurrence Theorem for category states that for a homeomorphism without open wandering sets, the set of non recurrent points forms a first category (meager) set. As an application of the effectivization of the Banach-Mazur game, we show that such a result holds true in effective settings as well.
Cite as

Prajval Koul and Satyadev Nandakumar. On Effective Banach-Mazur Games and an Application to the Poincaré Recurrence Theorem for Category. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 61:1-61:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koul_et_al:LIPIcs.STACS.2026.61,
  author =	{Koul, Prajval and Nandakumar, Satyadev},
  title =	{{On Effective Banach-Mazur Games and an Application to the Poincar\'{e} Recurrence Theorem for Category}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{61:1--61:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.61},
  URN =		{urn:nbn:de:0030-drops-255509},
  doi =		{10.4230/LIPIcs.STACS.2026.61},
  annote =	{Keywords: Recurrence, Topology, Category, Computable Analysis, Computable Toplogy, Dynamical Systems}
}
Document
DOI: 10.4230/LIPIcs.CSL.2026.24
Well-Founded Coalgebras Meet Kőnig’s Lemma

Authors: Henning Urbat and Thorsten Wißmann

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
Kőnig’s lemma is a fundamental result about trees with countless applications in mathematics and computer science. In contrapositive form, it states that if a tree is finitely branching and well-founded (i.e. has no infinite paths), then it is finite. We present a coalgebraic version of Kőnig’s lemma featuring two dimensions of generalization: from finitely branching trees to coalgebras for a finitary endofunctor H, and from the base category of sets to a locally finitely presentable category ℂ, such as the category of posets, nominal sets, or convex sets. Our coalgebraic Kőnig’s lemma states that, under mild assumptions on ℂ and H, every well-founded coalgebra for H is the directed join of its well-founded subcoalgebras with finitely generated state space - in particular, the category of well-founded coalgebras is locally presentable. As applications, we derive versions of Kőnig’s lemma for graphs in a topos as well as for nominal and convex transition systems. Additionally, we show that the key construction underlying the proof gives rise to two simple constructions of the initial algebra (equivalently, the final recursive coalgebra) for the functor H: The initial algebra is both the colimit of all well-founded and of all recursive coalgebras with finitely presentable state space. Remarkably, this result holds even in settings where well-founded coalgebras form a proper subclass of recursive ones. The first construction of the initial algebra is entirely new, while for the second one our approach yields a short and transparent new correctness proof.
Cite as

Henning Urbat and Thorsten Wißmann. Well-Founded Coalgebras Meet Kőnig’s Lemma. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{urbat_et_al:LIPIcs.CSL.2026.24,
  author =	{Urbat, Henning and Wi{\ss}mann, Thorsten},
  title =	{{Well-Founded Coalgebras Meet K\H{o}nig’s Lemma}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{24:1--24:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.24},
  URN =		{urn:nbn:de:0030-drops-254485},
  doi =		{10.4230/LIPIcs.CSL.2026.24},
  annote =	{Keywords: K\H{o}nig’s Lemma, Well-Foundedness, Coalgebra}
}
Document
DOI: 10.4230/DagRep.15.3.125
Weihrauch Complexity: Structuring the Realm of Non-Computability (Dagstuhl Seminar 25131)

Authors: Vasco Brattka, Alberto Marcone, Arno Pauly, Linda Westrick, and Kenneth Gill

Published in: Dagstuhl Reports, Volume 15, Issue 3 (2025)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 25131 "Weihrauch Complexity: Structuring the Realm of Non-Computability". It includes an abstract of every talk given during the seminar, as well as summaries of all presentations from the sessions on open problems and new research directions. At the end is the latest version of a bibliography on Weihrauch complexity which was originally started a decade ago at the first Dagstuhl Seminar on the topic (https://doi.org/10.4230/DagRep.5.9.77).
Cite as

Vasco Brattka, Alberto Marcone, Arno Pauly, Linda Westrick, and Kenneth Gill. Weihrauch Complexity: Structuring the Realm of Non-Computability (Dagstuhl Seminar 25131). In Dagstuhl Reports, Volume 15, Issue 3, pp. 125-158, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{brattka_et_al:DagRep.15.3.125,
  author =	{Brattka, Vasco and Marcone, Alberto and Pauly, Arno and Westrick, Linda and Gill, Kenneth},
  title =	{{Weihrauch Complexity: Structuring the Realm of Non-Computability (Dagstuhl Seminar 25131)}},
  pages =	{125--158},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{3},
  editor =	{Brattka, Vasco and Marcone, Alberto and Pauly, Arno and Westrick, Linda and Gill, Kenneth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.3.125},
  URN =		{urn:nbn:de:0030-drops-248965},
  doi =		{10.4230/DagRep.15.3.125},
  annote =	{Keywords: combinatorial problems, computability and complexity, computable analysis, reverse and constructive mathematics, Weihrauch reducibility and related reducibilities}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.48
Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform

Authors: Gabriele Fici and Estéban Gabory

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We define generalized de Bruijn words as those words having a Burrows-Wheeler transform that is a concatenation of permutations of the alphabet. We show that generalized de Bruijn words are in 1-to-1 correspondence with Hamiltonian cycles in the generalized de Bruijn graphs, introduced in the early '80s in the context of network design. When the size of the alphabet is a prime p, we define invertible necklaces as those whose BWT-matrix is non-singular. We show that invertible necklaces of length n correspond to normal bases of the finite field 𝔽_{pⁿ}, and that they form an Abelian group isomorphic to the Reutenauer group RG_pⁿ. Using known results in abstract algebra, we can make a bridge between generalized de Bruijn words and invertible necklaces. In particular, we highlight a correspondence between binary de Bruijn words of order d+1, binary necklaces of length 2^{d} having an odd number of 1’s, invertible BWT matrices of size 2^{d}× 2^{d}, and normal bases of the finite field 𝔽_{2^{2^{d}}}.
Cite as

Gabriele Fici and Estéban Gabory. Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fici_et_al:LIPIcs.MFCS.2025.48,
  author =	{Fici, Gabriele and Gabory, Est\'{e}ban},
  title =	{{Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.48},
  URN =		{urn:nbn:de:0030-drops-241555},
  doi =		{10.4230/LIPIcs.MFCS.2025.48},
  annote =	{Keywords: Burrows-Wheeler Transform, Generalized de Bruijn Word, Generalized de Bruijn Graph, Circulant Matrix, Invertible Necklace, Sandpile Group, Reutenauer Group}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.29
A Universal Uniform Approximation Theorem for Neural Networks

Authors: Olivier Bournez, Johanne Cohen, and Adrian Wurm

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We show the existence of a fixed recurrent network capable of approximating any computable function with arbitrary precision, provided that an encoding of the function is given in the initial input. While uniform approximation over a compact domain is a well-known property of neural networks, we go further by proving that our network ensures effective uniform approximation - simultaneously ensuring: - Uniform approximation in the sup-norm sense, guaranteeing precision across the compact domain {[0,1]^d}; - Uniformity in the sense of computability theory (also referred to as effectivity or universality), meaning the same network works for all computable functions. Our result is obtained constructively, using original arguments. Moreover, our construction bridges computation theory with neural network approximation, providing new insights into the fundamental connections between circuit complexity and function representation. Furthermore, this connection extends beyond computability to complexity theory. The obtained network is efficient: if a function is computable or approximable in polynomial time in the Turing machine model, then the network requires only a polynomial number of recurrences or iterations to achieve the same level of approximation, and conversely. Moreover, the recurrent network can be assumed to be very narrow, strengthening the link our results and existing models of very deep learning, where uniform approximation properties have already been established.
Cite as

Olivier Bournez, Johanne Cohen, and Adrian Wurm. A Universal Uniform Approximation Theorem for Neural Networks. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bournez_et_al:LIPIcs.MFCS.2025.29,
  author =	{Bournez, Olivier and Cohen, Johanne and Wurm, Adrian},
  title =	{{A Universal Uniform Approximation Theorem for Neural Networks}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{29:1--29:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.29},
  URN =		{urn:nbn:de:0030-drops-241365},
  doi =		{10.4230/LIPIcs.MFCS.2025.29},
  annote =	{Keywords: Models of computation, Complexity theory, Formal neural networks}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.79
Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space

Authors: Eike Neumann

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the problem of deciding whether a point escapes a closed subset of ℝ^d under the iteration of a continuous map f : ℝ^d → ℝ^d in the bit-model of real computation. We give a sound partial decision method for this problem which is complete in the sense that its halting set contains the halting set of all sound partial decision methods for the problem. Equivalently, our decision method terminates on all problem instances whose answer is robust under all sufficiently small perturbations of the function. We further show that the halting set of our algorithm is dense in the set of all problem instances. While our algorithm applies to general continuous functions, we demonstrate that it also yields complete decision methods for much more rigid function families: affine linear systems and quadratic complex polynomials. In the latter case, completeness is subject to the density of hyperbolicity conjecture in complex dynamics. This in particular yields an alternative proof of Hertling’s (2004) conditional answer to a question raised by Penrose (1989) regarding the computability of the Mandelbrot set.
Cite as

Eike Neumann. Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 79:1-79:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{neumann:LIPIcs.MFCS.2025.79,
  author =	{Neumann, Eike},
  title =	{{Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{79:1--79:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.79},
  URN =		{urn:nbn:de:0030-drops-241866},
  doi =		{10.4230/LIPIcs.MFCS.2025.79},
  annote =	{Keywords: Dynamical Systems, Computability in Analysis, Non-Linear Functions}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.91
Relative Randomness and Continuous Translation Functions

Authors: Ivan Titov

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
The notions of Martin-Löf randomness and of Solovay reducibility, as well as their relations to each other, are central objects of study in algorithmic randomness. When restricted to left-c.e. reals, Solovay reducibility of α to β can be characterized [Cristian S. Calude et al., 2001] as the existence of two left approximations a₀,a₁,… and b₀,b₁,… of α and β, respectively, such that the ratios (α-a_n)/(β-b_n) are bounded from above. By a celebrated result of Kučera and Slaman, among left-c.e. reals the Martin-Löf random ones are largest with respect to Solovay reducibility. The latter result was largely improved by the Limit Theorem of Barmpalias and Lewis-Pye [George Barmpalias and Andrew Lewis-Pye, 2017], which asserts that for given left-c.e. reals α and β where β is Martin-Löf random, for all left-approximations of α and β as above, the ratios (α-a_n)/(β-b_n) converge to the same limit. Though the original definition of Solovay reducibility applies to all reals, Solovay reducibility is considered to be badly behaved on the class of all reals. Accordingly, various variants of Solovay reducibility have been proposed, including variants defined via real-valued functions by Kumabe, Miyabe, and Suzuki [Kumabe et al., 2024] and a monotone variant by Titov [Titov, 2024]. It is known that for the monotone variant, the Limit Theorem of Barmpalias and Lewis-Pye extends to all reals [Titov, 2024]. By our main result, similarly the Limit Theorem holds for all reals with respect to the reducibility cl-open introduced by Kumabe et al. [Kumabe et al., 2024] in 2024. The result is formulated in terms of translation functions of bounded variation, and asserts that every such function from a Martin-Löf random real β to a real α is left differentiable in β. In a setting of functions that are required to be defined on the whole unit interval and not just on the reals strictly smaller than β, the differentiability of computable functions of bounded variation in every Martin-Löf random real was shown by Demuth [Demuth, 1975] in 1975; similar results for other types of computable functions and randomness notions were obtained by Brattka, Miller, and Nies [Vasco Brattka et al., 2011] in 2011 and Rute [Jason Rute, 2018] in 2018. Furthermore, we deduce from the main result an equivalent characterization of Martin-Löf randomness on the set of left-c.e. reals in terms of cl-open-reducibility of a real to itself.
Cite as

Ivan Titov. Relative Randomness and Continuous Translation Functions. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 91:1-91:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{titov:LIPIcs.MFCS.2025.91,
  author =	{Titov, Ivan},
  title =	{{Relative Randomness and Continuous Translation Functions}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{91:1--91:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.91},
  URN =		{urn:nbn:de:0030-drops-241987},
  doi =		{10.4230/LIPIcs.MFCS.2025.91},
  annote =	{Keywords: Solovay reducibility, relative randomness, algorithmic randomness, Martin-L\"{o}f randomness, computable analysis, left-c.e. reals}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.139
Minimality and Computability of Languages of G-Shifts

Authors: Djamel Eddine Amir and Benjamin Hellouin de Menibus

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Motivated by the notion of strong computable type for sets in computable analysis, we define the notion of strong computable type for G-shifts, where G is a finitely generated group with decidable word problem. A G-shift has strong computable type if one can compute its language from the complement of its language. We obtain a characterization of G-shifts with strong computable type in terms of a notion of minimality with respect to properties with a bounded computational complexity. We provide a self-contained direct proof, and also explain how this characterization can be obtained from an existing similar characterization for sets by Amir and Hoyrup, and discuss its connexions with results by Jeandel on closure spaces. We apply this characterization to several classes of shifts that are minimal with respect to specific properties. This provides a unifying approach that not only generalizes many existing results but also has the potential to yield new findings effortlessly. In contrast to the case of sets, we prove that strong computable type for G-shifts is preserved under products. We conclude by discussing some generalizations and future directions.
Cite as

Djamel Eddine Amir and Benjamin Hellouin de Menibus. Minimality and Computability of Languages of G-Shifts. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 139:1-139:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.ICALP.2025.139,
  author =	{Amir, Djamel Eddine and Hellouin de Menibus, Benjamin},
  title =	{{Minimality and Computability of Languages of G-Shifts}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{139:1--139:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.139},
  URN =		{urn:nbn:de:0030-drops-235161},
  doi =		{10.4230/LIPIcs.ICALP.2025.139},
  annote =	{Keywords: shifts, subshifts, minimal shifts, computable language, computability, strong computable type, descriptive complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.39
Tiling with Three Polygons Is Undecidable

Authors: Erik D. Demaine and Stefan Langerman

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We prove that the following problem is co-RE-complete and thus undecidable: given three simple polygons, is there a tiling of the plane where every tile is an isometry of one of the three polygons (either allowing or forbidding reflections)? This result improves on the best previous construction which requires five polygons.
Cite as

Erik D. Demaine and Stefan Langerman. Tiling with Three Polygons Is Undecidable. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.SoCG.2025.39,
  author =	{Demaine, Erik D. and Langerman, Stefan},
  title =	{{Tiling with Three Polygons Is Undecidable}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.39},
  URN =		{urn:nbn:de:0030-drops-231913},
  doi =		{10.4230/LIPIcs.SoCG.2025.39},
  annote =	{Keywords: plane tilings, polygons, undecidability, co-RE}
}
Document
DOI: 10.4230/DagRep.8.9.1
Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis (Dagstuhl Seminar 18361)

Authors: Vasco Brattka, Damir D. Dzhafarov, Alberto Marcone, and Arno Pauly

Published in: Dagstuhl Reports, Volume 8, Issue 9 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 18361 "Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis". It includes abstracts of talks presented during the seminar and open problems that were discussed, as well as a bibliography on Weihrauch complexity that was started during the previous meeting (Dagstuhl seminar 15392) and that saw some significant growth in the meantime. The session "Solved problems" is dedicated to the solutions to some of the open questions raised in the previous meeting (Dagstuhl seminar 15392).
Cite as

Vasco Brattka, Damir D. Dzhafarov, Alberto Marcone, and Arno Pauly. Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis (Dagstuhl Seminar 18361). In Dagstuhl Reports, Volume 8, Issue 9, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{brattka_et_al:DagRep.8.9.1,
  author =	{Brattka, Vasco and Dzhafarov, Damir D. and Marcone, Alberto and Pauly, Arno},
  title =	{{Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis (Dagstuhl Seminar 18361)}},
  pages =	{1--28},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{9},
  editor =	{Brattka, Vasco and Dzhafarov, Damir D. and Marcone, Alberto and Pauly, Arno},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.9.1},
  URN =		{urn:nbn:de:0030-drops-103270},
  doi =		{10.4230/DagRep.8.9.1},
  annote =	{Keywords: Computability and complexity in analysis, computations on real numbers, reducibilities, descriptive complexity, computational complexity, reverse and}
}
Document
DOI: 10.4230/DagRep.7.2.89
Computability Theory (Dagstuhl Seminar 17081)

Authors: Klaus Ambos-Spies, Vasco Brattka, Rodney Downey, and Steffen Lempp

Published in: Dagstuhl Reports, Volume 7, Issue 2 (2017)

Abstract
Computability is one of the fundamental notions of mathematics and computer science, trying to capture the effective content of mathematics and its applications. Computability Theory explores the frontiers and limits of effectiveness and algorithmic methods. It has its origins in Gödel's Incompleteness Theorems and the formalization of computability by Turing and others, which later led to the emergence of computer science as we know it today. Computability Theory is strongly connected to other areas of mathematics and theoretical computer science. The core of this theory is the analysis of relative computability and the induced degrees of unsolvability; its applications are mainly to Kolmogorov complexity and randomness as well as mathematical logic, analysis and algebra. Current research in computability theory stresses these applications and focuses on algorithmic randomness, computable analysis, computable model theory, and reverse mathematics (proof theory). Recent advances in these research directions have revealed some deep interactions not only among these areas but also with the core parts of computability theory. The goal of this Dagstuhl Seminar is to bring together researchers from all parts of computability theory and related areas in order to discuss advances in the individual areas and the interactions among those.
Cite as

Klaus Ambos-Spies, Vasco Brattka, Rodney Downey, and Steffen Lempp. Computability Theory (Dagstuhl Seminar 17081). In Dagstuhl Reports, Volume 7, Issue 2, pp. 89-101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{ambosspies_et_al:DagRep.7.2.89,
  author =	{Ambos-Spies, Klaus and Brattka, Vasco and Downey, Rodney and Lempp, Steffen},
  title =	{{Computability Theory (Dagstuhl Seminar 17081)}},
  pages =	{89--101},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{2},
  editor =	{Ambos-Spies, Klaus and Brattka, Vasco and Downey, Rodney and Lempp, Steffen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.2.89},
  URN =		{urn:nbn:de:0030-drops-73540},
  doi =		{10.4230/DagRep.7.2.89},
  annote =	{Keywords: algorithmic randomness, computability theory, computable algebra, computable analysis, generic case complexity, proof mining}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.17
Monte Carlo Computability

Authors: Vasco Brattka, Rupert Hölzl, and Rutger Kuyper

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We introduce Monte Carlo computability as a probabilistic concept of computability on infinite objects and prove that Monte Carlo computable functions are closed under composition. We then mutually separate the following classes of functions from each other: the class of multi-valued functions that are non-deterministically computable, that of Las Vegas computable functions, and that of Monte Carlo computable functions. We give natural examples of computational problems witnessing these separations. As a specific problem which is Monte Carlo computable but neither Las Vegas computable nor non-deterministically computable, we study the problem of sorting infinite sequences that was recently introduced by Neumann and Pauly. Their results allow us to draw conclusions about the relation between algebraic models and Monte Carlo computability.
Cite as

Vasco Brattka, Rupert Hölzl, and Rutger Kuyper. Monte Carlo Computability. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{brattka_et_al:LIPIcs.STACS.2017.17,
  author =	{Brattka, Vasco and H\"{o}lzl, Rupert and Kuyper, Rutger},
  title =	{{Monte Carlo Computability}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.17},
  URN =		{urn:nbn:de:0030-drops-70164},
  doi =		{10.4230/LIPIcs.STACS.2017.17},
  annote =	{Keywords: Weihrauch degrees, Weak Weak Konig's Lemma, Monte Carlo computability, algorithmic randomness, sorting}
}
Document
DOI: 10.4230/DagRep.5.9.77
Measuring the Complexity of Computational Content (Dagstuhl Seminar 15392)

Authors: Vasco Brattka, Akitoshi Kawamura, Alberto Marcone, and Arno Pauly

Published in: Dagstuhl Reports, Volume 5, Issue 9 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15392 "Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis." It includes abstracts on most talks presented during the seminar, a list of open problems that were discussed and partially solved during the meeting as well as a bibliography on the seminar topic that we compiled during the seminar.
Cite as

Vasco Brattka, Akitoshi Kawamura, Alberto Marcone, and Arno Pauly. Measuring the Complexity of Computational Content (Dagstuhl Seminar 15392). In Dagstuhl Reports, Volume 5, Issue 9, pp. 77-104, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{brattka_et_al:DagRep.5.9.77,
  author =	{Brattka, Vasco and Kawamura, Akitoshi and Marcone, Alberto and Pauly, Arno},
  title =	{{Measuring the Complexity of Computational Content (Dagstuhl Seminar 15392)}},
  pages =	{77--104},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{9},
  editor =	{Brattka, Vasco and Kawamura, Akitoshi and Marcone, Alberto and Pauly, Arno},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.9.77},
  URN =		{urn:nbn:de:0030-drops-56861},
  doi =		{10.4230/DagRep.5.9.77},
  annote =	{Keywords: Computability and complexity in analysis, computations on real numbers, reducibilities, descriptive complexity, computational complexity, reverse and constructive mathematics}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.130
Las Vegas Computability and Algorithmic Randomness

Authors: Vasco Brattka, Guido Gherardi, and Rupert Hölzl

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
In this article we try to formalize the question "What can be computed with access to randomness?" We propose the very fine-grained Weihrauch lattice as an approach to differentiate between different types of computation with access to randomness. In particular, we show that a natural concept of Las Vegas computability on infinite objects is more powerful than mere oracle access to a Martin-Löf random object. As a concrete problem that is Las Vegas computable but not computable with access to a Martin-Löf random oracle we study the problem of finding Nash equilibria.
Cite as

Vasco Brattka, Guido Gherardi, and Rupert Hölzl. Las Vegas Computability and Algorithmic Randomness. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 130-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{brattka_et_al:LIPIcs.STACS.2015.130,
  author =	{Brattka, Vasco and Gherardi, Guido and H\"{o}lzl, Rupert},
  title =	{{Las Vegas Computability and Algorithmic Randomness}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{130--142},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.130},
  URN =		{urn:nbn:de:0030-drops-49093},
  doi =		{10.4230/LIPIcs.STACS.2015.130},
  annote =	{Keywords: Weihrauch degrees, weak weak K\"{o}nig's lemma, Las Vegas computability, algorithmic randomness, Nash equilibria}
}
Document
DOI: 10.4230/DagRep.1.10.14
Computing with Infinite Data: Topological and Logical Foundations (Dagstuhl Seminar 11411)

Authors: Ulrich Berger, Vasco Brattka, Victor Selivanov, Dieter Spreen, and Hideki Tsuiki

Published in: Dagstuhl Reports, Volume 1, Issue 10 (2012)

Abstract
There is a large gap between mathematical structures and the structures computer implementations are based on. To stimulate research to overcome this---especially for infinitary structures---highly non-trivial problem the Dagstuhl Seminar 11411 ``Computing with Infinite Data: Topological and Logical Foundations'' was held. This report collects the ideas that were presented and discussed during the course of the seminar.
Cite as

Ulrich Berger, Vasco Brattka, Victor Selivanov, Dieter Spreen, and Hideki Tsuiki. Computing with Infinite Data: Topological and Logical Foundations (Dagstuhl Seminar 11411). In Dagstuhl Reports, Volume 1, Issue 10, pp. 14-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{berger_et_al:DagRep.1.10.14,
  author =	{Berger, Ulrich and Brattka, Vasco and Selivanov, Victor and Spreen, Dieter and Tsuiki, Hideki},
  title =	{{Computing with Infinite Data: Topological and Logical Foundations (Dagstuhl Seminar 11411)}},
  pages =	{14--36},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{1},
  number =	{10},
  editor =	{Berger, Ulrich and Brattka, Vasco and Selivanov, Victor and Spreen, Dieter and Tsuiki, Hideki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.10.14},
  URN =		{urn:nbn:de:0030-drops-33721},
  doi =		{10.4230/DagRep.1.10.14},
  annote =	{Keywords: Exact real number computation, Stream computation, Infinite computations, Computability in analysis, Hierarchies, Reducibility, Topological complexity}
}
  • Refine by Type
  • 18 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 7 2025
  • 1 2019
  • 2 2017
  • 1 2016
  • Show More...

  • Refine by Author
  • 10 Brattka, Vasco
  • 3 Gherardi, Guido
  • 3 Marcone, Alberto
  • 3 Pauly, Arno
  • 2 Hölzl, Rupert
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs
  • 2 OASIcs
  • 5 DagRep
  • 1 DagSemRep

  • Refine by Classification
  • 3 Theory of computation → Computability
  • 2 Theory of computation
  • 2 Theory of computation → Models of computation
  • 1 Computing methodologies → Neural networks
  • 1 Mathematics of computing → Combinatorics on words
  • Show More...

  • Refine by Keyword
  • 4 algorithmic randomness
  • 3 computable analysis
  • 3 descriptive complexity
  • 2 Computability and complexity in analysis
  • 2 Computable analysis
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact