Index sets for ω‐languages

An ω‐language is a set of infinite sequences (words) on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the languages, may enumerated as P₀, P₁, … and then an index set associated to a given property R (such as finiteness) of languages is just the set of e such that P_e has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language.     

A hierarchy of Turing degrees of divergence bounded computable real numbers

A real number x is f-bounded computable (f-bc, for short) for a function f if there is a computable sequence (x_s) of rational numbers which converges to x f-bounded effectively in the sense that, for any natural number n, the sequence (x_s) has at most f(n) non-overlapping jumps of size larger than 2^-n. f-bc reals are called divergence bounded computable if f is computable. In this paper we give a hierarchy theorem for Turing degrees of different classes of f-bc reals. More precisely, we will show that, for any computable functions f and g, if there exists a constant γ>1 such that, for any constant c, f(nγ)+n+cg(n) holds for almost all n, then the classes of Turing degrees given by f-bc and g-bc reals are different. As a corollary this implies immediately the result of [R. Rettinger, X. Zheng, On the Turing degrees of the divergence bounded computable reals, in: CiE 2005, June 8–15, Amsterdam, The Netherlands, Lecture Notes in Computer Science, vol. 3526, 2005, Springer, Berlin, pp. 418–428.] that the classes of Turing degrees of d-c.e. reals and divergence bounded computable reals are different.     

The elementary computable functions over the real numbers: applying two new techniques

The basic motivation behind this work is to tie together various computational complexity classes, whether over different domains such as the naturals or the reals, or whether defined in different manners, via function algebras (Real Recursive Functions) or via Turing Machines (Computable Analysis). We provide general tools for investigating these issues, using two techniques we call approximation and lifting. We use these methods to obtain two main theorems. First, we provide an alternative proof of the result from Campagnolo et al. (J Complex 18:977–1000, 2002), which precisely relates the Kalmar elementary computable functions to a function algebra over the reals. Second, we build on that result to extend a result of Bournez and Hainry (Theor Comput Sci 348(2–3):130–147, 2005), which provided a function algebra for the real elementary computable functions; our result does not require the restriction to functions. In addition to the extension, we provide an alternative approach to the proof. Their proof involves simulating the operation of a Turing Machine using a function algebra. We avoid this simulation, using a technique we call lifting, which allows us to lift the classic result regarding the elementary computable functions to a result on the reals. The two new techniques bring a different perspective to these problems, and furthermore appear more easily applicable to other problems of this sort.      

Ricci η‐recurrent real hypersurfaces in 2‐dimensional nonflat complex space forms

Let M be a Hopf hypersurface in a nonflat complex space form $M^2(c)$, $c\ne 0$, of complex dimension two. In this paper, we prove that M has η‐recurrent Ricci operator if and only if it is locally congruent to a homogeneous real hypersurface of type (A) or (B) or a non‐homogeneous real hypersurface with vanishing Hopf principal curvature. This is an extension of main results in [17, 21] for real hypersurfaces of dimension three. By means of this result, we give some new characterizations of Hopf hypersurfaces of type (A) and (B) which generalize those in [14, 18, 26].     

On effective σ‐boundedness and σ‐compactness

We prove several dichotomy theorems which extend some known results on σ‐bounded and σ‐compact pointsets. In particular we show that, given a finite number of $\Delta ^{1}_{1}$ equivalence relations $\mathrel {\mathsf {F}}_1,\dots ,\mathrel {\mathsf {F}}_n$, any $\Sigma ^{1}_{1}$ set A of the Baire space either is covered by compact $\Delta ^{1}_{1}$ sets and lightface $\Delta ^{1}_{1}$ equivalence classes of the relations $\mathrel {\mathsf {F}}_i$, or A contains a superperfect subset which is pairwise $\mathrel {\mathsf {F}}_i$‐inequivalent for all i = 1, …, n. Further generalizations to $\Sigma ^{1}_{2}$ sets A are obtained.     

σ‐short Boolean algebras

We introduce properties of Boolean algebras which are closely related to the existence of winning strategies in the Banach‐Mazur Boolean game. A σ‐short Boolean algebra is a Boolean algebra that has a dense subset in which every strictly descending sequence of length ω does not have a nonzero lower bound. We give a characterization of σ‐short Boolean algebras and study properties of σ‐short Boolean algebras. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

ω‐categorical weakly o‐minimal expansions of Boolean lattices

We study ω‐categorical weakly o‐minimal expansions of Boolean lattices. We show that a structure ?? = (A,≤, ?) expanding a Boolean lattice (A,≤) by a finite sequence I of ideals of A closed under the usual Heyting algebra operations is weakly o‐minimal if and only if it is ω‐categorical, and hence if and only if A/I has only finitely many atoms for every I ∈ ?. We propose other related examples of weakly o‐minimal ω‐categorical models in this framework, and we examine the internal structure of these models.     

S‐asymptotically ω‐periodic solutions for semilinear Volterra equations

We study S‐asymptotically ω‐periodic mild solutions of the semilinear Volterra equation u′(t)=(a* Au)(t)+f(t, u(t)), considered in a Banach space X, where A is the generator of an (exponentially) stable resolvent family. In particular, we extend the recent results for semilinear fractional integro‐differential equations considered in (Appl. Math. Lett. 2009; 22:865–870) and for semilinear Cauchy problems of first order given in (J. Math. Anal. Appl. 2008; 343(2): 1119–1130). Applications to integral equations arising in viscoelasticity theory are shown. Copyright © 2010 John Wiley & Sons, Ltd.     

Notes on local o‐minimality

We introduce and study some local versions of o‐minimality, requiring that every definable set decomposes as the union of finitely many isolated points and intervals in a suitable neighbourhood of every point. Motivating examples are the expansions of the ordered reals by sine, cosine and other periodic functions (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Sperner spaces and first‐order logic

We study the class of Sperner spaces, a generalized version of affine spaces, as defined in the language of pointline incidence and line parallelity. We show that, although the class of Sperner spaces is a pseudo‐elementary class, it is not elementary nor even ??_∞ω‐axiomatizable. We also axiomatize the first‐order theory of this class.     

On the Roots of σ‐Polynomials

Given a graph G of order n, the σ‐polynomial of G is the generating function where is the number of partitions of the vertex set of G into i nonempty independent sets. Such polynomials arise in a natural way from chromatic polynomials. Brenti (Trans Am Math Soc 332 (1992), 729–756) proved that σ‐polynomials of graphs with chromatic number at least had all real roots, and conjectured the same held for chromatic number . We affirm this conjecture.     

Characterization of g∞,σ‐integral operators

The application of the general tensor norms theory of Defant and Floret to the ideal of (p, σ)‐absolutely continuous operators of Matter, 0 < σ < 1, 1 ≤ p < ∞ leads to the study of g_p′,σ‐nuclear and g_p′,σ‐integral operators. Characterizations of such operators has been obtained previously in the case p > 1. In this paper we characterize the g_∞,σ‐nuclear and g_∞,σ‐integral operators by the existence of factorizations of some special kinds. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Admissible perturbations of α‐ψ‐pseudocontractive operators: convergence theorems

We prove some convergence theorems for α‐ψ‐pseudocontractive operators in real Hilbert spaces, by using the concept of admissible perturbation. Our results extend and complement some theorems in the existing literature. Copyright © 2016 John Wiley & Sons, Ltd.     

Pseudo asymptotically periodic mild solutions of semilinear functional integro‐differential equations in Banach spaces

In this paper, we introduce and investigate the functions of (μ,ν)‐pseudo S‐asymptotically ω‐periodic of class r(class infinity). We systematically explore the properties of these functions in Banach space including composition theorems. As applications, we establish some sufficient criteria for (μ,ν)‐pseudo S‐asymptotic ω‐periodicity of (nonautonomous) semilinear integro‐differential equations with finite or infinite delay. Finally, some interesting examples are presented to illustrate the main findings.     

Hierarchies in φ‐spaces and applications

We establish some results on the Borel and difference hierarchies in φ‐spaces. Such spaces are the topological counterpart of the algebraic directed‐complete partial orderings. E.g., we prove analogs of the Hausdorff Theorem relating the difference and Borel hierarchies and of the Lavrentyev Theorem on the non‐collapse of the difference hierarchy. Some of our results generalize results of A. Tang for the space Pω. We also sketch some older applications of these hierarchies and present a new application to the question of characterizing the ω‐ary Boolean operations generating a given level of the Wadge hierarchy from the open sets. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Filling certain cuts in discrete weakly o‐minimal structures

Discrete weakly o‐minimal structures, although not so stimulating as their dense counterparts, do exhibit a certain wealth of examples and pathologies. For instance they lack prime models and monotonicity for definable functions, and are not preserved by elementary equivalence. First we exhibit these features. Then we consider a countable theory of weakly o‐minimal structures with infinite definable discrete (convex) subsets and we study the Boolean algebra of definable sets of its countable models. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Boolean algebras of definable sets in weakly o‐minimal theories

We consider the sets definable in the countable models of a weakly o‐minimal theory T of totally ordered structures. We investigate under which conditions their Boolean algebras are isomorphic (hence T is p‐ω‐categorical), in other words when each of these definable sets admits, if infinite, an infinite coinfinite definable subset. We show that this is true if and only if T has no infinite definable discrete (convex) subset. We examine the same problem among arbitrary theories of mere linear orders. Finally we prove that, within expansions of Boolean lattices, every weakly o‐minimal theory is p‐ω‐categorical. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Coloring (gem, co‐gem)‐free graphs

A gem is a graph that consists of a path on four vertices plus a vertex adjacent to all four vertices of the path. A co‐gem is the complement of a gem. We prove that every (gem, co‐gem)‐free graph G satisfies the inequality (a special case of a conjecture of Gyárfás) and the inequality (a special case of a conjecture of Reed). Moreover, we give an ‐time algorithm that computes the chromatic number of any (gem, co‐gem)‐free graph with n vertices, while the existing algorithm in the literature takes .     

A (T,ψ)‐ψe decoupled scheme for a time‐dependent multiply‐connected eddy current problem

The aim of this paper is to develop a fully discrete ( T ,ψ)‐ψ_e finite element decoupled scheme to solve time‐dependent eddy current problems with multiply‐connected conductors. By making ‘cuts’ and setting jumps of ψ_e across the cuts in nonconductive domain, the uniqueness of ψ_e is guaranteed. Distinguished from the traditional T ‐ ψ method, our decoupled scheme solves the potentials T and ψ‐ ψ_e separately in two different simple equation systems, which avoids solving a saddle‐point equation system and leads to a remarkable reduction in computational efforts. The energy‐norm error estimate of the fully discrete decoupled scheme is provided. Finally, the scheme is applied to solve two benchmark problems—TEAM Workshop Problems 7 and IEEJ model. Copyright © 2013 John Wiley & Sons, Ltd.     

ω‐saturated quasi‐minimal models of Th(ℚω, +, σ, 0)

We show that (ℚ^ω, +, σ, 0) is a quasi-minimal torsion-free divisible abelian group. After discussing the axiomatization of the theory of this structure, we present its ω-saturated quasi-minimal model. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)