It is shown that the parity game can be solved in quasi-polynomial time. The parameterized parity game---with $n$ nodes and $m$ distinct values (a.k.a. colors or priorities)---is proven to be in the class of fixed parameter tractable problems when parameterized over $m$. Both results improve known bounds, from runtime $n^{O(\sqrt{n})}$ to $O(n^{\log(m)+6})$ and from an XP algorithm with runtime $O(n^{\Theta(m)})$ for fixed parameter $m$ to a fixed parameter tractable algorithm with runtime $O(n^5+2^{m\log(m)+6m})$. As an application, it is proven that colored Muller games with $n$ nodes and $m$ colors can be decided in time $O((m^m \cdot n)^5)$; it is also shown that this bound cannot be improved to $2^{o(m \cdot \log(m))} \cdot n^{O(1)}$ in the case that the exponential time hypothesis is true. Further investigations deal with memoryless Muller games and multidimensional parity games.

This paper introduces and studies a notion of \emph{algorithmic randomness} for subgroups of rationals. Given a randomly generated additive subgroup $(G,+)$ of rationals, two main questions are addressed: first, what are the model-theoretic and recursion-theoretic properties of $(G,+)$; second, what learnability properties can one extract from $G$ and its subclass of finitely generated subgroups? For the first question, it is shown that the theory of $(G,+)$ coincides with that of the additive group of integers and is therefore decidable; furthermore, while the word problem for $G$ with respect to any generating sequence for $G$ is not even semi-decidable, one can build a generating sequence $β$ such that the word problem for $G$ with respect to $β$ is co-recursively enumerable (assuming that the set of generators of $G$ is limit-recursive). In regard to the second question, it is proven that there is a generating sequence $β$ for $G$ such that every non-trivial finitely generated subgroup of $G$ is recursively enumerable and the class of all such subgroups of $G$ is behaviourally correctly learnable, that is, every non-trivial finitely generated subgroup can be semantically identified in the limit (again assuming that the set of generators of $G$ is limit-recursive). On the other hand, the class of non-trivial finitely generated subgroups of $G$ cannot be syntactically identified in the limit with respect to any generating sequence for $G$. The present work thus contributes to a recent line of research studying algorithmically random infinite structures and uncovers an interesting connection between the arithmetical complexity of the set of generators of a randomly generated subgroup of rationals and the learnability of its finitely generated subgroups.

It is shown that the parity game can be solved in quasipolynomial time. The parameterised parity game - with n nodes and m distinct values (aka colours or priorities) - is proven to be in the class of fixed parameter tractable (FPT) problems when parameterised over m. Both results improve known bounds, from runtime nO(√n) to O(nlog(m)+6) and from an XP-algorithm with runtime O(nΘ(m)) for fixed parameter m to an FPT-algorithm with runtime O(n5)+g(m), for some function g depending on m only. As an application it is proven that coloured Muller games with n nodes and m colours can be decided in time O((mm · n)5); it is also shown that this bound cannot be improved to O((2m · n)c), for any c, unless FPT = W[1].

Abstract In this paper, we investigate the existence of a Friedberg numbering in fragments of Peano Arithmetic and initial segments of Gödel's constructible hierarchyLα, whereαis Σ1admissible. We prove that (1) OverP−+BΣ2, the existence of a Friedberg numbering is equivalent toIΣ2, and (2) ForLα, there is a Friedberg numbering if and only if the tame Σ2projectum ofαequals the Σ2cofinality ofα.