Author name cluster

Rupert Hölzl

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2025 Journal Article

Computable classifications of continuous, transducer, and regular functions

Johanna N.Y. Franklin
Rupert Hölzl
Alexander Melnikov
Keng Meng Ng
Daniel Turetsky

We develop a systematic algorithmic framework that unites global and local classification problems using index sets. We prove that the classification problem for continuous (binary) regular functions among almost everywhere linear, pointwise linear-time Lipschitz functions is Σ 2 0 -complete. (Every regular function is pointwise linear-time Lipschitz.) We show that a function f: [ 0, 1 ] → R is (binary) transducer if and only if it is continuous regular. As one of many consequences, our Σ 2 0 -completeness result covers the class of transducer functions as well. Finally, we show that the Banach space C [ 0, 1 ] of real-valued continuous functions admits an arithmetical classification among separable Banach spaces. Our proofs combine methods of abstract computability theory, automata theory, and functional analysis.

Details DOI

TCS Journal 2018 Journal Article

Learning pattern languages over groups

Rupert Hölzl
Sanjay Jain
Frank Stephan

This article studies the learnability of classes of pattern languages over automatic groups. It is shown that the class of bounded unions of pattern languages over finitely generated Abelian automatic groups is explanatorily learnable. For patterns in which variables occur at most n times, it is shown that the classes of languages generated by such patterns as well as their bounded unions are, for finitely generated automatic groups, explanatorily learnable by an automatic learner. In contrast, automatic learners cannot learn the unions of up to two arbitrary pattern languages over the integers. Furthermore, there is an algorithm which, given an automaton describing a group G, generates a learning algorithm M G such that either M G explanatorily learns all pattern languages over G or there is no learner for this set of languages at all, not even a non-recursive one. For some automatic groups, non-learnability results of natural classes of pattern languages are provided.

Details DOI

I&C Journal 2015 Journal Article

Probabilistic computability and choice

Vasco Brattka
Guido Gherardi
Rupert Hölzl

We study the computational power of randomized computations on infinite objects, such as real numbers. In particular, we introduce the concept of a Las Vegas computable multi-valued function, which is a function that can be computed on a probabilistic Turing machine that receives a random binary sequence as auxiliary input. The machine can take advantage of this random sequence, but it always has to produce a correct result or to stop the computation after finite time if the random advice is not successful. With positive probability the random advice has to be successful. We characterize the class of Las Vegas computable functions in the Weihrauch lattice with the help of probabilistic choice principles and Weak Weak Kőnig's Lemma. Among other things we prove an Independent Choice Theorem that implies that Las Vegas computable functions are closed under composition. In a case study we show that Nash equilibria are Las Vegas computable, while zeros of continuous functions with sign changes cannot be computed on Las Vegas machines. However, we show that the latter problem admits randomized algorithms with weaker failure recognition mechanisms. The last mentioned results can be interpreted such that the Intermediate Value Theorem is reducible to the jump of Weak Weak Kőnig's Lemma, but not to Weak Weak Kőnig's Lemma itself. These examples also demonstrate that Las Vegas computable functions form a proper superclass of the class of computable functions and a proper subclass of the class of non-deterministically computable functions. We also study the impact of specific lower bounds on the success probabilities, which leads to a strict hierarchy of classes. In particular, the classical technique of probability amplification fails for computations on infinite objects. We also investigate the dependency on the underlying probability space. Besides Cantor space, we study the natural numbers, the Euclidean space and Baire space.

Details DOI

I&C Journal 2014 Journal Article

Initial segment complexities of randomness notions

Rupert Hölzl
Thorsten Kräling
Frank Stephan
Guohua Wu

Schnorr famously proved that Martin-Löf-randomness of a sequence A can be characterised via the complexity of Aʼs initial segments. Nies, Stephan and Terwijn as well as independently Miller showed that a set is 2-random (that is, Martin-Löf random relative to the halting problem K) iff there is no function f such that for all m and all n > f ( m ) it holds that C ( A ( 0 ) A ( 1 ) … A ( n ) ) ⩽ n − m; before the proof of this equivalence the notion defined via the latter condition was known as Kolmogorov random. In the present work it is shown that characterisations of this style can also be given for other randomness criteria like strong randomness (also known as weak 2-randomness), Kurtz randomness relative to K, Martin-Löf randomness of PA-incomplete sets, and strong Kurtz randomness; here one does not just quantify over all functions f but over functions f of a specific form. For example, A is Martin-Löf random and PA-incomplete iff there is no A-recursive function f such that for all m and all n > f ( m ) it holds that C ( A ( 0 ) A ( 1 ) … A ( n ) ) ⩽ n − m. The characterisation for strong randomness relates to functions which are the concatenation of an A-recursive function executed after a K-recursive function; this solves an open problem of Nies. In addition to this, characterisations of a similar style are also given for Demuth randomness, weak Demuth randomness and Schnorr randomness relative to K. Although the unrelativised versions of Kurtz randomness and Schnorr randomness do not admit such a characterisation in terms of plain Kolmogorov complexity, Bienvenu and Merkle gave one in terms of Kolmogorov complexity defined by computable machines.

Details DOI