20 Search Results for "Pauly, Arno"

Document
DOI: 10.4230/LIPIcs.LICS.2026.77
Problems with Fixpoints of Polynomials of Polynomials

Authors: Cécilia Pradic and Ian Price

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract
Motivated by applications in computable analysis, we study fixpoints of certain endofunctors over categories of containers. More specifically, we focus on fibred endofunctors over the fibrewise opposite of the codomain fibration that can be themselves be represented by families of polynomial endofunctors. In this setting, we show how to compute initial algebras, terminal coalgebras and another kind of fixpoint ζ. We then explore a number of examples of derived operators inspired by Weihrauch complexity and the usual construction of the free polynomial monad. We introduce ζ-expressions as the syntax of μ-bicomplete categories, extended with ζ-binders and parallel products, which thus have a natural denotation in containers. By interpreting certain ζ-expressions in a category of type-2 computable maps, we are able to capture a number of meaningful Weihrauch degrees, ranging from closed choice on {0,1} to determinacy of infinite parity games, via an "answerable part" operator.
Cite as

Cécilia Pradic and Ian Price. Problems with Fixpoints of Polynomials of Polynomials. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 77:1-77:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{pradic_et_al:LIPIcs.LICS.2026.77,
  author =	{Pradic, C\'{e}cilia and Price, Ian},
  title =	{{Problems with Fixpoints of Polynomials of Polynomials}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{77:1--77:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.77},
  URN =		{urn:nbn:de:0030-drops-268642},
  doi =		{10.4230/LIPIcs.LICS.2026.77},
  annote =	{Keywords: Polynomial functors, containers, fixpoints, Weihrauch complexity}
}
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.31
Games with ω-Automatic Preference Relations

Authors: Véronique Bruyère, Christophe Grandmont, and Jean-François Raskin

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

Abstract
This paper investigates Nash equilibria (NEs) in multi-player turn-based games on graphs, where player preferences are modeled as ω-automatic relations via deterministic parity automata. Unlike much of the existing literature, which focuses on specific reward functions, our results apply to any preference relation definable by an ω-automatic relation. We analyze the computational complexity of determining the existence of an NE (possibly under some constraints), verifying whether a given strategy profile forms an NE, and checking whether a specific outcome can be realized by an NE. When a (constrained) NE exists, we show that there always exists one with finite-memory strategies. Finally, we explore fundamental properties of ω-automatic relations and their implications in the existence of equilibria.
Cite as

Véronique Bruyère, Christophe Grandmont, and Jean-François Raskin. Games with ω-Automatic Preference Relations. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bruyere_et_al:LIPIcs.MFCS.2025.31,
  author =	{Bruy\`{e}re, V\'{e}ronique and Grandmont, Christophe and Raskin, Jean-Fran\c{c}ois},
  title =	{{Games with \omega-Automatic Preference Relations}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{31:1--31:19},
  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.31},
  URN =		{urn:nbn:de:0030-drops-241381},
  doi =		{10.4230/LIPIcs.MFCS.2025.31},
  annote =	{Keywords: Games played on graphs, Nash equilibrium, \omega-automatic relations, \omega-recognizable relations, constrained Nash equilibria existence problem}
}
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.CONCUR.2025.12
The Non-Cooperative Rational Synthesis Problem for SPEs and ω-Regular Objectives

Authors: Véronique Bruyère, Jean-François Raskin, Alexis Reynouard, and Marie Van Den Bogaard

Published in: LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025)

Abstract
This paper studies the rational synthesis problem for multi-player games played on graphs when rational players are following subgame perfect equilibria. In these games, one player, the system, declares his strategy upfront, and the other players, composing the environment, then rationally respond by playing strategies forming a subgame perfect equilibrium. We study the complexity of the rational synthesis problem when the players have ω-regular objectives encoded as parity objectives. Our algorithm is based on an encoding into a three-player game with imperfect information, showing that the problem is in 2ExpTime. When the number of environment players is fixed, the problem is in ExpTime and is NP- and coNP-hard. Moreover, for a fixed number of players and reachability objectives, we get a polynomial algorithm.
Cite as

Véronique Bruyère, Jean-François Raskin, Alexis Reynouard, and Marie Van Den Bogaard. The Non-Cooperative Rational Synthesis Problem for SPEs and ω-Regular Objectives. In 36th International Conference on Concurrency Theory (CONCUR 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 348, pp. 12:1-12:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bruyere_et_al:LIPIcs.CONCUR.2025.12,
  author =	{Bruy\`{e}re, V\'{e}ronique and Raskin, Jean-Fran\c{c}ois and Reynouard, Alexis and Van Den Bogaard, Marie},
  title =	{{The Non-Cooperative Rational Synthesis Problem for SPEs and \omega-Regular Objectives}},
  booktitle =	{36th International Conference on Concurrency Theory (CONCUR 2025)},
  pages =	{12:1--12:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-389-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{348},
  editor =	{Bouyer, Patricia and van de Pol, Jaco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.12},
  URN =		{urn:nbn:de:0030-drops-239622},
  doi =		{10.4230/LIPIcs.CONCUR.2025.12},
  annote =	{Keywords: non-zero-sum games, subgame perfect equilibria, rational synthesis}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2025.21
Quantitative Language Automata

Authors: Thomas A. Henzinger, Pavol Kebis, Nicolas Mazzocchi, and N. Ege Saraç

Published in: LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025)

Abstract
A quantitative word automaton (QWA) defines a function from infinite words to values. For example, every infinite run of a limit-average QWA 𝒜 obtains a mean payoff, and every word w ∈ Σ^ω is assigned the maximal mean payoff obtained by nondeterministic runs of 𝒜 over w. We introduce quantitative language automata (QLAs) that define functions from language generators (i.e., implementations) to values, where a language generator can be nonprobabilistic, defining a set of infinite words, or probabilistic, defining a probability measure over infinite words. A QLA consists of a QWA and an aggregator function. For example, given a QWA 𝒜, the infimum aggregator maps each language L ⊆ Σ^ω to the greatest lower bound assigned by 𝒜 to any word in L. For boolean value sets, QWAs define boolean properties of traces, and QLAs define boolean properties of sets of traces, i.e., hyperproperties. For more general value sets, QLAs serve as a specification language for a generalization of hyperproperties, called quantitative hyperproperties. A nonprobabilistic (resp. probabilistic) quantitative hyperproperty assigns a value to each set (resp. distribution) G of traces, e.g., the minimal (resp. expected) average response time exhibited by the traces in G. We give several examples of quantitative hyperproperties and investigate three paradigmatic problems for QLAs: evaluation, nonemptiness, and universality. In the evaluation problem, given a QLA 𝔸 and an implementation G, we ask for the value that 𝔸 assigns to G. In the nonemptiness (resp. universality) problem, given a QLA 𝔸 and a value k, we ask whether 𝔸 assigns at least k to some (resp. every) language. We provide a comprehensive picture of decidability for these problems for QLAs with common aggregators as well as their restrictions to ω-regular languages and trace distributions generated by finite-state Markov chains.
Cite as

Thomas A. Henzinger, Pavol Kebis, Nicolas Mazzocchi, and N. Ege Saraç. Quantitative Language Automata. In 36th International Conference on Concurrency Theory (CONCUR 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 348, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.CONCUR.2025.21,
  author =	{Henzinger, Thomas A. and Kebis, Pavol and Mazzocchi, Nicolas and Sara\c{c}, N. Ege},
  title =	{{Quantitative Language Automata}},
  booktitle =	{36th International Conference on Concurrency Theory (CONCUR 2025)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-389-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{348},
  editor =	{Bouyer, Patricia and van de Pol, Jaco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.21},
  URN =		{urn:nbn:de:0030-drops-239718},
  doi =		{10.4230/LIPIcs.CONCUR.2025.21},
  annote =	{Keywords: Quantitative hyperproperties, quantitative automata, automata-based verification}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.59
Formalizing Hyperspaces for Extracting Efficient Exact Real Computation

Authors: Michal Konečný, Sewon Park, and Holger Thies

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We propose a framework for certified computation on hyperspaces by formalizing various higher-order data types and operations in a constructive dependent type theory. Our approach builds on our previous work on axiomatization of exact real computation where we formalize nondeterministic first-order partial computations over real and complex numbers. Based on the axiomatization, we first define open, closed, compact and overt subsets in an abstract topological way that allows short and elegant proofs with computational content coinciding with standard definitions in computable analysis. From these proofs we extract programs for testing inclusion, overlapping of sets, et cetera. To improve extracted programs, our framework specializes the Euclidean space ℝ^m making use of metric properties. To define interesting operations over hyperspaces of Euclidean space, we introduce a nondeterministic version of a continuity principle valid under the standard type-2 realizability interpretation. Instead of choosing one of the usual formulations, we define it in a way similar to an interval extension operator, which often is already available in exact real computation software. We prove that the operations on subsets preserve the encoding, and thereby define a small calculus to built new subsets from given ones, including limits of converging sequences with regards to the Hausdorff metric. From the proofs, we extract programs that generate drawings of subsets of ℝ^m with any given precision efficiently. As an application we provide a function that constructs fractals, such as the Sierpinski triangle, from iterated function systems using the limit operation, resulting in certified programs that errorlessly draw such fractals up to any desired resolution.
Cite as

Michal Konečný, Sewon Park, and Holger Thies. Formalizing Hyperspaces for Extracting Efficient Exact Real Computation. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 59:1-59:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{konecny_et_al:LIPIcs.MFCS.2023.59,
  author =	{Kone\v{c}n\'{y}, Michal and Park, Sewon and Thies, Holger},
  title =	{{Formalizing Hyperspaces for Extracting Efficient Exact Real Computation}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{59:1--59:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.59},
  URN =		{urn:nbn:de:0030-drops-185935},
  doi =		{10.4230/LIPIcs.MFCS.2023.59},
  annote =	{Keywords: Computable analysis, type theory, program extraction}
}
Document
DOI: 10.4230/DagRep.11.10.72
Descriptive Set Theory and Computable Topology (Dagstuhl Seminar 21461)

Authors: Mathieu Hoyrup, Arno Pauly, Victor Selivanov, and Mariya I. Soskova

Published in: Dagstuhl Reports, Volume 11, Issue 10 (2022)

Abstract
Computability and continuity are closely linked - in fact, continuity can be seen as computability relative to an arbitrary oracle. As such, concepts from topology and descriptive set theory feature heavily in the foundations of computable analysis. Conversely, techniques developed in computability theory can be fruitfully employed in topology and descriptive set theory, even if the desired results mention no computability at all. In this Dagstuhl Seminar, we brought together researchers from computable analysis, from classical computability theory, from descriptive set theory, formal topology, and other relevant areas. Our goals were to identify key open questions related to this interplay, to exploit synergies between the areas and to intensify collaboration between the relevant communities.
Cite as

Mathieu Hoyrup, Arno Pauly, Victor Selivanov, and Mariya I. Soskova. Descriptive Set Theory and Computable Topology (Dagstuhl Seminar 21461). In Dagstuhl Reports, Volume 11, Issue 10, pp. 72-93, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{hoyrup_et_al:DagRep.11.10.72,
  author =	{Hoyrup, Mathieu and Pauly, Arno and Selivanov, Victor and Soskova, Mariya I.},
  title =	{{Descriptive Set Theory and Computable Topology (Dagstuhl Seminar 21461)}},
  pages =	{72--93},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{11},
  number =	{10},
  editor =	{Hoyrup, Mathieu and Pauly, Arno and Selivanov, Victor and Soskova, Mariya I.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.10.72},
  URN =		{urn:nbn:de:0030-drops-159293},
  doi =		{10.4230/DagRep.11.10.72},
  annote =	{Keywords: computable analysis, enumeration degrees, quasi-polish spaces, synthetic topology}
}
Document
DOI: 10.4230/LIPIcs.CSL.2021.22
Computing Measure as a Primitive Operation in Real Number Computation

Authors: Christine Gaßner, Arno Pauly, and Florian Steinberg

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)

Abstract
We study the power of BSS-machines enhanced with abilities such as computing the measure of a BSS-decidable set or computing limits of BSS-computable converging sequences. Our variations coalesce into just two equivalence classes, each of which also can be described as a lower cone in the Weihrauch degrees. We then classify computational tasks such as computing the measure of Δ⁰₂-set of reals, integrating piece-wise continuous functions and recovering a continuous function from an L₁([0, 1])-description. All these share the Weihrauch degree lim.
Cite as

Christine Gaßner, Arno Pauly, and Florian Steinberg. Computing Measure as a Primitive Operation in Real Number Computation. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganer_et_al:LIPIcs.CSL.2021.22,
  author =	{Ga{\ss}ner, Christine and Pauly, Arno and Steinberg, Florian},
  title =	{{Computing Measure as a Primitive Operation in Real Number Computation}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{22:1--22:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.22},
  URN =		{urn:nbn:de:0030-drops-134564},
  doi =		{10.4230/LIPIcs.CSL.2021.22},
  annote =	{Keywords: BSS-machine, Weihrauch reducibility, integrable function, Lebesgue measure, computable analysis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.8
Descriptive Complexity on Non-Polish Spaces

Authors: Antonin Callard and Mathieu Hoyrup

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Represented spaces are the spaces on which computations can be performed. We investigate the descriptive complexity of sets in represented spaces. We prove that the standard representation of a countably-based space preserves the effective descriptive complexity of sets. We prove that some results from descriptive set theory on Polish spaces extend to arbitrary countably-based spaces. We study the larger class of coPolish spaces, showing that their representation does not always preserve the complexity of sets, and we relate this mismatch with the sequential aspects of the space. We study in particular the space of polynomials.
Cite as

Antonin Callard and Mathieu Hoyrup. Descriptive Complexity on Non-Polish Spaces. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{callard_et_al:LIPIcs.STACS.2020.8,
  author =	{Callard, Antonin and Hoyrup, Mathieu},
  title =	{{Descriptive Complexity on Non-Polish Spaces}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.8},
  URN =		{urn:nbn:de:0030-drops-118694},
  doi =		{10.4230/LIPIcs.STACS.2020.8},
  annote =	{Keywords: Represented space, Computable analysis, Descriptive set theory, CoPolish spaces}
}
Document
DOI: 10.4230/LIPIcs.CSL.2020.34
Computing Haar Measures

Authors: Arno Pauly, Dongseong Seon, and Martin Ziegler

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
According to Haar’s Theorem, every compact topological group G admits a unique (regular, right and) left-invariant Borel probability measure μ_G. Let the Haar integral (of G) denote the functional ∫_G:?(G)∋ f ↦ ∫ f d μ_G integrating any continuous function f:G → ℝ with respect to μ_G. This generalizes, and recovers for the additive group G=[0;1)mod 1, the usual Riemann integral: computable (cmp. Weihrauch 2000, Theorem 6.4.1), and of computational cost characterizing complexity class #P_1 (cmp. Ko 1991, Theorem 5.32). We establish that in fact, every computably compact computable metric group renders the Haar measure/integral computable: once using an elegant synthetic argument, exploiting uniqueness in a computably compact space of probability measures; and once presenting and analyzing an explicit, imperative algorithm based on "maximum packings" with rigorous error bounds and guaranteed convergence. Regarding computational complexity, for the groups SO(3) and SU(2), we reduce the Haar integral to and from Euclidean/Riemann integration. In particular both also characterize #P_1.
Cite as

Arno Pauly, Dongseong Seon, and Martin Ziegler. Computing Haar Measures. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{pauly_et_al:LIPIcs.CSL.2020.34,
  author =	{Pauly, Arno and Seon, Dongseong and Ziegler, Martin},
  title =	{{Computing Haar Measures}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.34},
  URN =		{urn:nbn:de:0030-drops-116779},
  doi =		{10.4230/LIPIcs.CSL.2020.34},
  annote =	{Keywords: Computable analysis, topological groups, exact real arithmetic, Haar measure}
}
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/LIPIcs.FSTTCS.2018.38
Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions

Authors: Stéphane Le Roux, Arno Pauly, and Mickael Randour

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
We study finite-memory (FM) determinacy in games on finite graphs, a central question for applications in controller synthesis, as FM strategies correspond to implementable controllers. We establish general conditions under which FM strategies suffice to play optimally, even in a broad multi-objective setting. We show that our framework encompasses important classes of games from the literature, and permits to go further, using a unified approach. While such an approach cannot match ad-hoc proofs with regard to tightness of memory bounds, it has two advantages: first, it gives a widely-applicable criterion for FM determinacy; second, it helps to understand the cornerstones of FM determinacy, which are often hidden but common in proofs for specific (combinations of) winning conditions.
Cite as

Stéphane Le Roux, Arno Pauly, and Mickael Randour. Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{leroux_et_al:LIPIcs.FSTTCS.2018.38,
  author =	{Le Roux, St\'{e}phane and Pauly, Arno and Randour, Mickael},
  title =	{{Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.38},
  URN =		{urn:nbn:de:0030-drops-99373},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.38},
  annote =	{Keywords: games on graphs, finite-memory determinacy, multiple objectives}
}
Document
DOI: 10.4230/LIPIcs.CSL.2018.10
Beyond Admissibility: Dominance Between Chains of Strategies

Authors: Nicolas Basset, Ismaël Jecker, Arno Pauly, Jean-François Raskin, and Marie Van den Bogaard

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Abstract
Admissible strategies, i.e. those that are not dominated by any other strategy, are a typical rationality notion in game theory. In many classes of games this is justified by results showing that any strategy is admissible or dominated by an admissible strategy. However, in games played on finite graphs with quantitative objectives (as used for reactive synthesis), this is not the case. We consider increasing chains of strategies instead to recover a satisfactory rationality notion based on dominance in such games. We start with some order-theoretic considerations establishing sufficient criteria for this to work. We then turn our attention to generalised safety/reachability games as a particular application. We propose the notion of maximal uniform chain as the desired dominance-based rationality concept in these games. Decidability of some fundamental questions about uniform chains is established.
Cite as

Nicolas Basset, Ismaël Jecker, Arno Pauly, Jean-François Raskin, and Marie Van den Bogaard. Beyond Admissibility: Dominance Between Chains of Strategies. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{basset_et_al:LIPIcs.CSL.2018.10,
  author =	{Basset, Nicolas and Jecker, Isma\"{e}l and Pauly, Arno and Raskin, Jean-Fran\c{c}ois and Van den Bogaard, Marie},
  title =	{{Beyond Admissibility: Dominance Between Chains of Strategies}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.10},
  URN =		{urn:nbn:de:0030-drops-96774},
  doi =		{10.4230/LIPIcs.CSL.2018.10},
  annote =	{Keywords: dominated strategies, admissible strategies, games played on finite graphs, reactive synthesis, reachability games, safety games, cofinal, order theory}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CONCUR.2017.2
Admissibility in Games with Imperfect Information (Invited Talk)

Authors: Romain Brenguier, Arno Pauly, Jean-François Raskin, and Ocan Sankur

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract
In this invited paper, we study the concept of admissible strategies for two player win/lose infinite sequential games with imperfect information. We show that in stark contrast with the perfect information variant, admissible strategies are only guaranteed to exist when players have objectives that are closed sets. As a consequence, we also study decision problems related to the existence of admissible strategies for regular games as well as finite duration games.
Cite as

Romain Brenguier, Arno Pauly, Jean-François Raskin, and Ocan Sankur. Admissibility in Games with Imperfect Information (Invited Talk). In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{brenguier_et_al:LIPIcs.CONCUR.2017.2,
  author =	{Brenguier, Romain and Pauly, Arno and Raskin, Jean-Fran\c{c}ois and Sankur, Ocan},
  title =	{{Admissibility in Games with Imperfect Information}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.2},
  URN =		{urn:nbn:de:0030-drops-78066},
  doi =		{10.4230/LIPIcs.CONCUR.2017.2},
  annote =	{Keywords: Admissibility, non-zero sum games, reactive synthesis, imperfect infor- mation}
}
  • Refine by Type
  • 20 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2023
  • 1 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 13 Pauly, Arno
  • 5 Raskin, Jean-François
  • 3 Brattka, Vasco
  • 3 Marcone, Alberto
  • 2 Bruyère, Véronique
  • Show More...

  • Refine by Series/Journal
  • 15 LIPIcs
  • 1 OASIcs
  • 4 DagRep

  • Refine by Classification
  • 3 Theory of computation → Automata over infinite objects
  • 2 Mathematics of computing → Point-set topology
  • 2 Theory of computation
  • 2 Theory of computation → Constructive mathematics
  • 2 Theory of computation → Logic
  • Show More...

  • Refine by Keyword
  • 5 computable analysis
  • 3 Computable analysis
  • 2 Computability and complexity in analysis
  • 2 Descriptive set theory
  • 2 Nash equilibrium
  • 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