Recent zbMATH articles in MSC 03Dhttps://zbmath.org/atom/cc/03D2021-06-15T18:09:00+00:00WerkzeugCompositions of multivalued functions.https://zbmath.org/1460.030132021-06-15T18:09:00+00:00"Goh, Jun Le"https://zbmath.org/authors/?q=ai:goh.jun-leComparison of mathematical theorems up to Weihrauch reducibility is closely related to an inverse mathematics program that studies the proof-theoretic power of mathematical theorems over some basic theory. The standard base theory is a weak subsystem of second-order arithmetic known as \(\mathrm{RCA}_0\), which roughly corresponds to computable mathematics. In this context, the following questions arise: for any two theorems \(P, Q\), theorem \(P\) is Weihrauch reducible to theorem \(Q\) or for different \(Q_0,\dots,Q_{n-1}\) theorem \(P\) is Weihrauch reducible to theorems \(Q_0,\dots,Q_{n-1}\) in series over \(\mathrm{RCA}_0\). The author studies such questions from the point of view of Weihrauch reducibility and introduces some reducibility information that clarifies the reducibility of \(P\) to multiple sequential instances of \(Q\). The author defines some reducibility which would capture the notion of \(P\) being reducible to multiple instances of \(Q\) in series, where \(P\), \(Q\), \(\bar{Q}\), etc., refer multivalued functions from \(\mathbb{N} ^{\mathbb{N}}\) to \(\mathbb{N} ^{\mathbb{N}}\). There are three ways to formalize this idea: composition work, reducibility play. The author gives sufficient conditions for the equivalence of reducibility and proves that they are in general, they are not equivalent.
Reviewer: Jamalbek Tussupov (Astana)An \(\omega \)-REA set forming a minimal pair with 0'.https://zbmath.org/1460.030122021-06-15T18:09:00+00:00"Gerdes, Peter"https://zbmath.org/authors/?q=ai:gerdes.peter-mShore has noted that
(*) the Turing degree of an \(\omega\)-REA set and \(\mathbf 0''\) cannot form a minimal pair
and raised the question of whether \(\mathbf 0'\) could replace \(\mathbf 0''\) in (*). The main theorem of this paper answers Shore's question negatively, constructing a set as described in the title. The author also shows, in a different direction, that (*) holds for \(\mathbf 0''\) with any \(\alpha\) in place of \(\omega\).
Reviewer: Leon Harkleroad (Bowdoinham)Transducer degrees: atoms, infima and suprema.https://zbmath.org/1460.030112021-06-15T18:09:00+00:00"Endrullis, Jörg"https://zbmath.org/authors/?q=ai:endrullis.jorg"Klop, Jan Willem"https://zbmath.org/authors/?q=ai:klop.jan-willem"Bakhshi, Rena"https://zbmath.org/authors/?q=ai:bakhshi.renaThe contribution investigates finite-state transducers on infinite words and utilizes their computed functions in the spirit known from reductions in the area of computability and complexity theory. More precisely, an infinite sequence \(v\) reduces to another infinite sequence \(w\) if and only if there exists a finite state transducer that transforms \(v\) into \(w\). As usual this introduces a preorder on infinite sequences with two streams equivalent if they interreduce. The equivalence classes of this equivalence relation are called transducer degrees. The preorder naturally induces a partial order on the transducer degrees and the contribution investigates the structure of this partial order in detail.
The paper surveys the existing results and techniques, identifies the smallest transducer degree and the atomic degrees, which are the degrees just above the smallest degree. It also investigates whether infima and surprema exist and in which cases they exist, because in general the authors demonstrate that they do not exist. Finally, they are also interested in infinite chains of ascending and descending degrees. Actually, when restricted to computable transducer degrees it is also demonstrated that a largest degree exists. Many questions remain open and the general questions are often only solved for very special classes and instances.
The paper is well written and exposes the general topic and research question succinctly. The development becomes technical rather quickly and assumes some familiarity with finite-state transducers but otherwise remains understandable to any computer-science graduate.
Reviewer: Andreas Maletti (Leipzig)Randomness and Solovay degrees.https://zbmath.org/1460.030142021-06-15T18:09:00+00:00"Miyabe, Kenshi"https://zbmath.org/authors/?q=ai:miyabe.kenshi"Nies, Andre"https://zbmath.org/authors/?q=ai:nies.andre-otfrid"Stephan, Frank"https://zbmath.org/authors/?q=ai:stephan.frankSchnorr randomness is a weaker version of Martin-Löf randomness. It is well known that Schnorr randomness is quite different the Martin-Löf one. In the paper under review, some further results were proved to demonstrate the difference. For example, it is a classical result that left c.e. Martin-Löf randomness is upward closed under Solovay reduction. But the authors showed that it is not for Schnorr randomness. Further more, there is a left c.e. Schnorr random real which can split into two left c.e. non-normal reals having effective Hausdorff dimension 0.
Reviewer: Liang Yu (Nanjing)Minimal weak truth table degrees and computably enumerable Turing degrees.https://zbmath.org/1460.030022021-06-15T18:09:00+00:00"Downey, Rodney G."https://zbmath.org/authors/?q=ai:downey.rodney-graham"Ng, Keng Meng"https://zbmath.org/authors/?q=ai:ng.kengmeng"Solomon, Reed"https://zbmath.org/authors/?q=ai:solomon.reedTwo of the main partially ordered structures studied in computability theory are the structure of Turing degrees (\(T\)-degrees) and the structure of weak truth-table degrees (\(wtt\)-degrees). Both structures have minimal elements.
A \(T\)-degree or \(wtt\)-degree is called \textit{computably enumerable} (c.e.) if it contains a c.e. set. A known basic result is that the partially ordered substructures of c.e. \(wtt\)-degrees and c.e. \(T\)-degrees are dense.
In the book under review, the authors analyze how minimal \(wtt\)-degrees interact with c.e. \(T\)-degrees.
From the density of c.e. \(T\)- or \(wtt\)-degrees and by the fact that weak truth-table reducibility is included in Turing reducibility it follows that there are no sets with minimal \(T\)-degree which wtt-bound noncomputable c.e. sets.
In contrast, the authors show that there are sets with minimal wtt-degree which \(T\)-bound noncomputable c.e. sets, namely:
(1) There exists a \(\Delta^0_2\)-set \(A\) with minimal \(wtt\)-degree which \(T\)-bounds a noncomputable c.e. set \(B\).
In the proof of (1) \(A\) is constructed by a full approximation argument with a priority tree of strategies, combined with permitting method to build \(B\) such that \(B\le_T A\). The proof is very involved and a preliminary chapter is dedicated to a useful informal description of it.
The second part of the book contains two other main results, which provide two limitations on (1):
(2) No c.e. \(T\)-degree can contain a set with minimal \(wtt\)-degree, that is sets \(A\) that realize (1) can \(T\)-bound a c.e. set only strictly;
(3) Let \(V\) be a promptly simple set and let \(A\) be a \(\Delta^0_2\)-set such that \(V\le_T A\). There exists a noncomputable c.e. set \(B\) such that \(B\le_{wtt} A\).
By (3), all \(\Delta^0_2\)-sets which \(T\)-bound a promptly simple set are excluded in (1).
Reviewer: Patrizio Cintioli (Camerino)Average-case bit-complexity theory of real functions.https://zbmath.org/1460.030162021-06-15T18:09:00+00:00"Schröder, Matthias"https://zbmath.org/authors/?q=ai:schroder.matthias"Steinberg, Florian"https://zbmath.org/authors/?q=ai:steinberg.florian"Ziegler, Martin"https://zbmath.org/authors/?q=ai:ziegler.martinSummary: We introduce, and initiate the study of, average-case bit-complexity theory over the reals: like in the discrete case a first, naïve notion of polynomial average runtime turns out to lack robustness and is thus refined. Standard examples of explicit continuous functions with increasingly high worst-case complexity are shown to be in fact easy in the mean; while a further example is constructed with both worst and average complexity exponential: for topological/metric reasons, i.e., oracles do not help. The notions are then generalized from the reals to represented spaces; and, in the real case, related to randomized computation.
For the entire collection see [Zbl 1334.68018].On the computational complexity of positive linear functionals on \(\mathcal{C}[0;1]\).https://zbmath.org/1460.030152021-06-15T18:09:00+00:00"Férée, Hugo"https://zbmath.org/authors/?q=ai:feree.hugo"Ziegler, Martin"https://zbmath.org/authors/?q=ai:ziegler.martinSummary: The Lebesgue integration has been related to polynomial counting complexity in several ways, even when restricted to smooth functions. We prove analogue results for the integration operator associated with the Cantor measure as well as a more general second-order \({\mathbf {\mathsf{\#P}}}\)-hardness criterion for such operators. We also give a simple criterion for relative polynomial time complexity and obtain a better understanding of the complexity of integration operators using the Lebesgue decomposition theorem.
For the entire collection see [Zbl 1334.68018].Using Taylor models in exact real arithmetic.https://zbmath.org/1460.650492021-06-15T18:09:00+00:00"Brauße, Franz"https://zbmath.org/authors/?q=ai:brausse.franz"Korovina, Margarita"https://zbmath.org/authors/?q=ai:korovina.margarita-vladimirovna"Müller, Norbert"https://zbmath.org/authors/?q=ai:muller.norbert-thSummary: Software libraries for exact real arithmetic implement the theory of computability on non-denumerable sets. Usually they are based on interval arithmetic. We discuss enhancements where the interval arithmetic is augmented by versions of Taylor models. Although this has no effect on the abstract notion of computability, the efficiency of implementations can be improved dramatically.
For the entire collection see [Zbl 1334.68018].Complexity theory for spaces of integrable functions.https://zbmath.org/1460.030172021-06-15T18:09:00+00:00"Steinberg, Florian"https://zbmath.org/authors/?q=ai:steinberg.florianSummary: This paper investigates second-order representations in the sense of Kawamura and Cook for spaces of integrable functions that regularly show up in analysis. It builds upon prior work about the space of continuous functions on the unit interval: Kawamura and Cook introduced a representation inducing the right complexity classes and proved that it is the weakest second-order representation such that evaluation is polynomial-time computable.
The first part of this paper provides a similar representation for the space of integrable functions on a bounded subset of Euclidean space: The weakest representation rendering integration over boxes is polynomial-time computable. In contrast to the representation of continuous functions, however, this representation turns out to be discontinuous with respect to both the norm and the weak topology.
The second part modifies the representation to be continuous and generalizes it to \(L_p\)-spaces. The arising representations are proven to be computably equivalent to the standard representations of these spaces as metric spaces and to still render integration polynomial-time computable. The family is extended to cover Sobolev spaces on the unit interval, where less basic operations like differentiation and some Sobolev embeddings are shown to be polynomial-time computable.
Finally as a further justification quantitative versions of the Arzelà-Ascoli and Fréchet-Kolmogorov Theorems are presented and used to argue that these representations fulfill a minimality condition. To provide tight bounds for the Fréchet-Kolmogorov Theorem, a form of exponential time computability of the norm of \(L^p\) is proven.LTL to self-loop alternating automata with generic acceptance and back.https://zbmath.org/1460.680492021-06-15T18:09:00+00:00"Blahoudek, František"https://zbmath.org/authors/?q=ai:blahoudek.frantisek"Major, Juraj"https://zbmath.org/authors/?q=ai:major.juraj"Strejček, Jan"https://zbmath.org/authors/?q=ai:strejcek.janSummary: Self-loop alternating automata (SLAA) with Büchi or co-Büchi acceptance are popular formalisms also known as very weak alternating automata (VWAA). They are often used as an intermediate results in translations of LTL to deterministic or nondeterministic automata. This paper considers SLAA with generic transition-based Emerson-Lei acceptance and presents translations of LTL to these automata and back. Importantly, the translation of LTL to SLAA with generic acceptance produces considerably smaller automata than previous translations of LTL to Büchi or co-Büchi SLAA. Our translation is already implemented in the tool ltl3tela, where it helps to produce small deterministic or nondeterministic transition-based Emerson-Lei automata for given LTL formulae.Grilliot's trick in nonstandard analysis.https://zbmath.org/1460.030042021-06-15T18:09:00+00:00"Sanders, Sam"https://zbmath.org/authors/?q=ai:sanders.samSummary: Recently, \textit{D. Normann} and the author have established a connection between \textit{higher-order computability theory} and \textit{Nonstandard Analysis}; new results in both fields are obtained by exploiting this connection [J. Symb. Log. 84, No. 4, 1422--1465 (2019; Zbl 1454.03018)]. Now, on the side of computability theory, the technique known as \textit{Grilliot's trick} constitutes a template for explicitly defining the Turing jump functional \((\exists^2)\) in terms of a given effectively discontinuous type two functional [\textit{T. J. Grilliot}, J. Symb. Log. 36, 245--248 (1971; Zbl 0224.02034)]. In light of the aforementioned connection, it is a natural question what corresponds to Grilliot's trick in Nonstandard Analysis? In this paper, we discuss the \textit{nonstandard extensionality trick}: a technique similar to Grilliot's trick in Nonstandard Analysis. This nonstandard trick proceeds by deriving from the existence of certain \textit{nonstandard discontinuous} functionals, the \textit{Transfer} principle from Nonstandard analysis limited to \(\Pi^0_1\)-formulas; from this (generally ineffective) implication, we obtain an effective implication expressing the Turing jump functional in terms of a discontinuous functional (and no longer involving Nonstandard Analysis). The advantage of our nonstandard approach is that \textit{one obtains effective content without paying attention to effective content}. We also discuss a new class of functionals which fall outside the established categories. These functionals derive from the \textit{Standard Part} axiom of Nonstandard Analysis.Universal insertion grammars of size two.https://zbmath.org/1460.680472021-06-15T18:09:00+00:00"Verlan, Sergey"https://zbmath.org/authors/?q=ai:verlan.sergey"Fernau, Henning"https://zbmath.org/authors/?q=ai:fernau.henning"Kuppusamy, Lakshmanan"https://zbmath.org/authors/?q=ai:kuppusamy.lakshmananSummary: In this paper, we show that pure insertion grammars of size 2 (i.e., inserting two symbols in a left and right context, each consisting of two symbols) can characterize all recursively enumerable languages. This is achieved by either applying an inverse morphism and a weak coding, or a left (right) quotient with a regular LOC(2) language, or an intersection with a LOC(2) language and a weak coding. The obtained results improve the descriptional complexity of insertion grammars and complete the picture of known results on insertion-deletion systems that are motivated from the DNA computing area.