Bounded iteration and unary functions

The set of unary functions of complexity classes defined by using bounded primitive recursion is inductively characterized by means of bounded iteration. Elementary unary functions, linear space computable unary functions and polynomial space computable unary functions are then inductively characterized using only composition and bounded iteration. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A recursion-theoretic approach to NP

An implicit characterization of the class NP is given, without using any minimization scheme. This is the first purely recursion-theoretic formulation of NP.     

Subrecursive functions on partial sequences

The paper studies a domain theoretical notion of primitive recursion over partial sequences in the context of Scott domains. Based on a non-monotone coding of partial sequences, this notion supports a rich concept of parallelism in the sense of Plotkin. The complexity of these functions is analysed by a hierarchy of classes similar to the Grzegorczyk classes. The functions considered are characterised by a function algebra generated by continuity preserving operations starting from computable initial functions. Its layers are related to those above by showing , thus generalising results of Schwichtenberg/Müller and Niggl. Received: 18 November 1996     

The equivalence of bar recursion and open recursion

Several extensions of Gödel's system T$\mathsf{T}$ with new forms of recursion have been designed for the purpose of giving a computational interpretation to classical analysis. One can organise many of these extensions into two groups: those based on bar recursion, which include Spector's original bar recursion, modified bar recursion and the more recent products of selections functions, or those based on open recursion   which in particular include the symmetric Berardi–Bezem–Coquand (BBC) functional. We relate these two groups by showing that both open recursion and the BBC functional are primitive recursively equivalent to a variant of modified bar recursion. Our results, in combination with existing research, essentially complete the classification up to primitive recursive equivalence of those extensions of system T$\mathsf{T}$ used to give a direct computational interpretation to choice principles.     

Light Dialectica revisited

We upgrade the light Dialectica interpretation (Hernest, 2005) [6] by adding two more light universal quantifiers, which are both semi-computational and semi-uniform and complement each other. An illustrative example is presented for the new light quantifiers and a new application is given for the older uniform quantifier. The realizability of new light negative formulations for the Axiom of Choice and for the Independence of Premises is explored in the new setting.     

Positivity and matrix semigroups

We study various aspects of how certain positivity assumptions on complex matrix semigroups affect their structure. Our main result is that every irreducible group of complex matrices with nonnegative diagonal entries is simultaneously similar to a group of weighted permutations. We also consider the corresponding question for semigroups and discuss the effect of the assumption that a fixed linear functional has nonnegative values when restricted to a given semigroup.     

Jackson theorems for generalized polynomials with special applications to trigonometric and hyperbolic functions

Jackson theorems for polynomials are transformed into Jackson theorems for more general function classes by way of special operators. In particular, Jackson-Timan and inverse theorems are shown for classes of trigonometric and hyperbolic functions.     

Jensen inequalities for functions with higher monotonicities

Summary We investigate generalizations of the classical Jensen and Chebyshev inequalities. On one hand, we restrict the class of functions and on the other we enlarge the class of measures which are allowed. As an example, consider the inequality (J)(f(x) d) A (f(x) d, d d = 1. Iff is an arbitrary nonnegativeL _x function, this holds if 0, is convex andA = 1. Iff is monotone the measure need not be positive for (J) to hold for all convex withA = 1. If has higher monotonicity, e.g., is also convex, then we get a version of (J) withA < 1 and measures that need not be positive.     

Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones

Let T() be the ordinal notation system from Buchholz-Schütte (1988). [The order type of the countable segmentT()₀ is — by Rathjen (1988) — the proof-theoretic ordinal the proof-theoretic ordinal ofACA ₀ + ( ₁ ^l –TR).] In particular let _a denote the enumeration function of the infinite cardinals and leta ₀ a denote the partial collapsing operation on T() which maps ordinals of T() into the countable segment T ₀ of T(). Assume that the (fast growing) extended Grzegorczyk hierarchy and the slow growing hierarchy are defined with respect to the natural system of distinguished fundamental sequences of Buchholz and Schütte (1988) in the following way:

Short propositional refutations for dense random 3CNF formulas

Random 3CNF formulas constitute an important distribution for measuring the average-case behavior of propositional proof systems. Lower bounds for random 3CNF refutations in many propositional proof systems are known. Most notable are the exponential-size resolution refutation lower bounds for random 3CNF formulas with Ω(n^1.5−ε)$\mathrm{\Omega }(n^{1.5-\epsilon })$ clauses (Chvátal and Szemerédi [14], Ben-Sasson and Wigderson [10]). On the other hand, the only known non-trivial upper bound on the size of random 3CNF refutations in a non-abstract propositional proof system is for resolution with Ω(n²/log?n)$\mathrm{\Omega }(n^2/\log ?n)$ clauses, shown by Beame et al. [6]. In this paper we show that already standard propositional proof systems, within the hierarchy of Frege proofs, admit short refutations for random 3CNF formulas, for sufficiently large clause-to-variable ratio. Specifically, we demonstrate polynomial-size propositional refutations whose lines are TC⁰${\mathit{T}\mathit{C}}^0$ formulas (i.e., TC⁰${\mathit{T}\mathit{C}}^0$-Frege proofs) for random 3CNF formulas with n   variables and Ω(n^1.4)$\mathrm{\Omega }(n^{1.4})$ clauses.     

About new analogies of Gronwall–Bellman–Bihari type inequalities for discontinuous functions and estimated solutions for impulsive differential systems

In this article we present new integral Gronwall–Bellman–Bihari type inequalities for discontinuous functions (integro-sum inequalities). As applications, we investigate estimated solutions for impulsive differential systems, conditions of boundedness, stability, practical stability.     

About some new integral inequalities of Wendroff type for discontinuous functions

In this article, we obtain some new nonlinear integral inequalities for discontinuous functions of two independent variables (Wendroff type) by including also inequalities with delay. We deduce new generalizations of earlier results given by R.P. Agarwal, R. Bellman, I. Bihari, B.K. Bondge, V. Lakshmikantham, S. Leela, B.G. Pachpatte for continuous and discrete functions. Furthermore, generalizations of some results for integro-sum inequalities are obtained as well.     

The $\mu$-measure as a tool for classifying computational complexity

Two simply typed term systems and are considered, both for representing algorithms computing primitive recursive functions. is based on primitive recursion, on recursion on notation. A purely syntactical method of determining the computational complexity of algorithms in , called $\mu$ -measure, is employed to uniformly integrate traditional results in subrecursion theory with resource-free characterisations of sub-elementary complexity classes. Extending the Schwichtenberg and Müller characterisation of the Grzegorczyk classes for , it is shown $\mathcal{E}_{n+1} = \mathcal{R}^n_1n\ge 1\mathcal{R}^n_i$ denotes the \emph{th modified Heinermann class} based on . The proof does not refer to any machine-based computation model, unlike the Schwichtenberg and Müller proofs. This is due to the notion of modified recursion lying on top of each other provided by . By Ritchie's result, characterises the linear-space computable functions. Using the same method, a short and straightforward proof is presented, showing that characterises the polynomial time computable functions. Furthermore, the classes and coincide at and above level 2. Received: 22 September 1997 / Revised version: 12 May 1999     

A restricted computation model on Scott domains and its partial primitive recursive functionals

The paper builds on both a simply typed term system and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions and PTWP are studied that are closed under scvr. The twist are certain type 1 G?del recursors for simultaneous partial primitive recursion. Formally, denotes a function , however, is modelled such that is finite, or in other words, a partial sequence. As for PTWP, the concept of type writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP-computable functionals coincide with those definable in plus a constant for sequential minimisation. In particular, the functionals definable in denoted can be characterised by a subclass of PTWP-computable functionals denoted . Moreover, hierarchies of strictly increasing classes in the style of Heinermann and complexity classes are introduced such that . These results extend those for and PTWP [Nig94]. Finally, scvr is employed to define for each type the enumeration functional of all finite elements of . Received January 30, 1996     

The normal subgroup lattice of 2-transitive automorphism groups of linearly ordered sets

Using combinatorial and model-theoretic means, we examine the structure of normal subgroup lattices N(A()) of 2-transitive automorphism groups A() of infinite linearly ordered sets (, ). Certain natural sublattices of N(A()) are shown to be Stone algebras, and several first order properties of their dense and dually dense elements are characterized within the Dedekind-completion of (, ). As a consequence, A() has either precisely 5 or at least 2²¹ (even maximal) normal subgroups, and various other group- and lattice-theoretic results follow.     

Algebraic semantics and model completeness for Intuitionistic Public Announcement Logic

In the present paper, we start studying epistemic updates using the standard toolkit of duality theory. We focus on public announcements, which are the simplest epistemic actions, and hence on Public Announcement Logic (PAL) without the common knowledge operator. As is well known, the epistemic action of publicly announcing a given proposition is semantically represented as a transformation of the model encoding the current epistemic setup of the given agents; the given current model being replaced with its submodel relativized to the announced proposition. We dually characterize the associated submodel-injection map as a certain pseudo-quotient map between the complex algebras respectively associated with the given model and with its relativized submodel. As is well known, these complex algebras are complete atomic BAOs (Boolean algebras with operators). The dual characterization we provide naturally generalizes to much wider classes of algebras, which include, but are not limited to, arbitrary BAOs and arbitrary modal expansions of Heyting algebras (HAOs). Thanks to this construction, the benefits and the wider scope of applications given by a point-free, intuitionistic theory of epistemic updates are made available. As an application of this dual characterization, we axiomatize the intuitionistic analogue of PAL, which we refer to as IPAL, prove soundness and completeness of IPAL w.r.t. both algebraic and relational models, and show that the well known Muddy Children Puzzle can be formalized in IPAL.     

Equivalence of bar induction and bar recursion for continuous functions with continuous moduli

We compare Brouwer's bar theorem and Spector's bar recursion for the lowest type in the context of constructive reverse mathematics. To this end, we reformulate bar recursion as a logical principle stating the existence of a bar recursor for every function which serves as the stopping condition of bar recursion. We then show that the decidable bar induction is equivalent to the existence of a bar recursor for every continuous function from ${\mathbb{N}}^{\mathbb{N}}$ to $\mathbb{N}$ with a continuous modulus. We also introduce fan recursion, the bar recursion for binary trees, and show that the decidable fan theorem is equivalent to the existence of a fan recursor for every continuous function from ${\{0,1\}}^{\mathbb{N}}$ to $\mathbb{N}$ with a continuous modulus. The equivalence for bar induction holds over the extensional version of intuitionistic arithmetic in all finite types augmented with the characteristic principles of Gödel's Dialectica interpretation. On the other hand, we show the equivalence for fan theorem without using such extra principles.     

The complexity of central series in nilpotent computable groups

The terms of the upper and lower central series of a nilpotent computable group have computably enumerable Turing degree. We show that the Turing degrees of these terms are independent even when restricted to groups which admit computable orders.