An Interval of Computably Enumerable Isolating Degrees

We construct computably enumerable degrees a < b such that all computably enumerable degrees c with a < c < b isolate some d. c. e. degree d.     

Isolation and the Jump Operator

We show the existence of a high d. c. e. degree d and a low₂ c.e. degree a such that d is isolated by a .     

The low<Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> and low<Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> r. e. degrees are not elementarily equivalent

Jockusch, Li and Yang showed that the Lown and Low1 r.e. degrees are not elementarily equivalent for n > 1. We answer a question they raise by using the results of Nies, Shore and Slaman to show that the Lown and Lowm r.e. degrees are not elementarily equivalent for n > m > 1.     

Non‐isolated quasi‐degrees

We show that non‐isolated from below 2‐c.e. Q ‐degrees are dense in the structure of c.e. Q ‐degrees. We construct a 2‐c.e. Q ‐degree, which can't be isolated from below not only by c.e. Q ‐degrees, but by any Q ‐degree. We also prove that below any c.e. Q ‐degree there is a 2‐c.e. Q ‐degree, which is non‐isolated from below and from above (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

There is No Low Maximal D.C.E. Degree

We show that for any computably enumerable (c.e.) set A and any set L, if L is low and , then there is a c.e. splitting such that . In Particular, if L is low and n‐c.e., then is n‐c.e. and hence there is no low maximal n‐c.e. degree.     

Splitting in 2-computably enumerable degrees with avoiding cones

In this paper we show that for any pair of properly 2-c. e. degrees 0 < d < a such that there are no c. e. degrees between d and a, the degree a is splittable in the class of 2-c. e. degrees avoiding the upper cone of d. We also study the possibility to characterize such an isolation in terms of splitting.     

Effectively and Noneffectively Nowhere Simple Sets

R. Shore proved that every recursively enumerable (r. e.) set can be split into two (disjoint) nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ? of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two (non) effectively nowhere simple sets, and r. e. sets which can be split into two r. e. non-nowhere simple sets. We show that every r. e. set is either the disjoint union of two effectively nowhere simple sets or two noneffectively nowhere simple sets. We characterize r. e. sets whose every nontrivial splitting is into nowhere simple sets, and r. e. sets whose every nontrivial splitting is into effectively nowhere simple sets. R. Shore proved that for every effectively nowhere simple set A, the lattice L* (A) is effectively isomorphic to ?*, and that there is a nowhere simple set A such that L*(A) is not effectively isomorphic to ?*. We prove that every nonzero r. e. Turing degree contains a noneffectively nowhere simple set A with the lattice L*(A) effectively isomorphic to ?*. Mathematics Subject Classification: 03D25, 03D10.     

Reductions between types of numberings

This paper considers reductions between types of numberings; these reductions preserve the Rogers Semilattice of the numberings reduced and also preserve the number of minimal and positive degrees in their semilattice. It is shown how to use these reductions to simplify some constructions of specific semilattices. Furthermore, it is shown that for the basic types of numberings, one can reduce the left-r.e. numberings to the r.e. numberings and the k-r.e. numberings to the $(k+1)$-r.e. numberings; all further reductions are obtained by concatenating these reductions.     

On the bounded quasi‐degrees of c.e. sets

We study the degree structure of bQ‐reducibility and we prove that for any noncomputable c.e. incomplete bQ‐degree a, there exists a nonspeedable bQ‐degree incomparable with it. The structure $\mathcal {D}_{\mbox{bs}}$ of the $\mbox{bs}$‐degrees is not elementary equivalent neither to the structure of the $\mbox{be}$‐degrees nor to the structure of the $\mbox{e}$‐degrees. If c.e. degrees a and b form a minimal pair in the c.e. bQ‐degrees, then a and b form a minimal pair in the bQ‐degrees. Also, for every simple set S there is a noncomputable nonspeedable set A which is bQ‐incomparable with S and bQ‐degrees of S and A does not form a minimal pair.     

Development and application of Halanay-type theory: Evolutionary differential and difference equations with time lag

We consider extensions, developments and modifications of a result due to Halanay, and the application of “Halanay-type inequalities” in the analysis and numerics of retarded functional-differential equations, difference equations, and retarded functional-difference equations. Our emphasis is on the variety, structure and development, and future development, of Halanay-type results and their applications. We classify and present novel results of Halanay type (linear and non-linear, discrete, semi-discrete, and continuous) and establish their relevance to delay-differential equations, discretized analogues (we consider ?-methods), and difference equations. A rôle for such results in stability and contractivity analysis is made apparent.     

Endomorphisms of the shift dynamical system, discrete derivatives, and applications

All continuous endomorphisms f_∞ of the shift dynamical system S on the 2-adic integers Z₂ are induced by some , where n is a positive integer, B_n is the set of n-blocks over {0, 1}, and f_∞(x)=y₀y₁y₂… where for all i∈N, y_i=f(x_ix_i+1…x_i+n−1). Define D:Z₂→Z₂ to be the endomorphism of S induced by the map {(00,0),(01,1),(10,1),(11,0)} and V:Z₂→Z₂ by V(x)=−1−x. We prove that D, V°D, S, and V°S are conjugate to S and are the only continuous endomorphisms of S whose parity vector function is solenoidal. We investigate the properties of D as a dynamical system, and use D to construct a conjugacy from the 3x+1 function T:Z₂→Z₂ to a parity-neutral dynamical system. We also construct a conjugacy R from D to T. We apply these results to establish that, in order to prove the 3x+1 conjecture, it suffices to show that for any m∈Z⁺, there exists some n∈N such that R⁻¹(m) has binary representation of the form or .     

Frame cellular automata: Configurations, generating sets and related matroids

We introduce a frame cellular automaton as a broad generalization of an earlier study on quasigroup-defined cellular automata. It consists of a triple (F,R,E_F) where, for a given finite set X of cells, the frame F is a family of subsets of X (called elementary frames, denoted S_i, i=1,…,n), which is a cover of X. A matching configuration is a map which attributes to each cell a state in a finite set G under restriction of a set of local rules R={R_i∣i=1,…n}, where R_i holds in the elementary frame S_i and is determined by an (|S_i|-1)-ary quasigroup over G. The frame associated map E_F models how a matching configuration can be grown iteratively from a certain initial cell-set. General properties of frames and related matroids are investigated. A generating set S⊂X is a set of cells such that there is a bijection between the collection of matching configurations and G^S. It is shown that for certain frames, the algebraically defined generating sets are bases of a related geometric-combinatorially defined matroid.     

Rationalization and the Gray index of phantom maps

In this paper we study a homotopy invariant of phantom maps called the Gray index. We give a new interpretation of the Gray index of a phantom map f:X→Y, in terms of the rationalization of X. We use this interpretation, in order to detect phantom maps of a specific Gray index. Finally, we examine the set of phantom maps with infinite Gray index in a tower theoretic way.     

Scattering matrices of regular coverings of graphs

We give a decomposition formula for the determinant on the bond scattering matrix of a regular covering of G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we express the determinant on the bond scattering matrix of a regular covering of G by means of its L-functions.     

DFT calculation for the {2}-inverse of a polynomial matrix with prescribed image and kernel

In this paper, we first give the finite algorithm for generalized inverse of a matrix A over an integral domain, and, based on it and the discrete Fourier transform, present an algorithm for calculating {2}-inverses of a polynomial matrix with prescribed image and kernel. And the algorithm is implemented in the Mathematica programming language and expands the algorithms in [13].     

Minimax theorems and applications to the existence and uniqueness of solutions of some differential equations

In this paper, minimax theorems due to Stepan A. Tersian were generalized, the existence and uniqueness of solutions for several semilinear equations were proved by employing our generalized theorems, and the existence and uniqueness results of nonresonance problem for these semilinear equations under the asymptotic un-uniformity conditions were presented.     

On the colored Tutte polynomial of a graph of bounded treewidth

We observe that a formula given by Negami [Polynomial invariants of graphs, Trans. Amer. Math. Soc. 299 (1987) 601-622] for the Tutte polynomial of a k-sum of two graphs generalizes to a colored Tutte polynomial. Consequently, an algorithm of Andrzejak [An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Math. 190 (1998) 39-54] may be directly adapted to compute the colored Tutte polynomial of a graph of bounded treewidth in polynomial time. This result has also been proven by Makowsky [Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Discrete Appl. Math. 145 (2005) 276-290], using a different algorithm based on logical techniques.     

Nonlinear structure of some classical quasi-Banach spaces and -spaces

We investigate the Lipschitz structure of ℓ_p and L_p for 0<p<1 as quasi-Banach spaces and as metric spaces (with the metric induced by the p-norm) and show that they are not Lipschitz isomorphic. We prove that the -space L₀ is not uniformly homeomorphic to any other L_p space, that the L_p spaces for 0<p<1 embed isometrically into one another, and reduce the problem of the uniform equivalence amongst L_p spaces to their Lipschitz equivalence as metric spaces.     

A distance-labelling problem for hypercubes

Let i₁≥i₂≥i₃≥1 be integers. An L(i₁,i₂,i₃)-labelling of a graph G=(V,E) is a mapping ?:V→{0,1,2,…} such that |?(u)−?(v)|≥i_t for any u,v∈V with d(u,v)=t, t=1,2,3, where d(u,v) is the distance in G between u and v. The integer ?(v) is called the label assigned to v under ?, and the difference between the largest and the smallest labels is called the span of ?. The problem of finding the minimum span, λ_i1,i2,i3(G), over all L(i₁,i₂,i₃)-labellings of G arose from channel assignment in cellular communication systems, and the related problem of finding the minimum number of labels used in an L(i₁,i₂,i₃)-labelling was originated from recent studies on the scalability of optical networks. In this paper we study the L(i₁,i₂,i₃)-labelling problem for hypercubes Q_d (d≥3) and obtain upper and lower bounds on λ_i1,i2,i3(Q_d) for any (i₁,i₂,i₃).     

Identities between q-hypergeometric and hypergeometric integrals of different dimensions

Given complex numbers m₁,l₁ and nonnegative integers m₂,l₂, such that m₁+m₂=l₁+l₂, for any a,b=0,…,min(m₂,l₂) we define an l₂-dimensional Barnes type q-hypergeometric integral I_a,b(z,μ;m₁,m₂,l₁,l₂) and an l₂-dimensional hypergeometric integral J_a,b(z,μ;m₁,m₂,l₁,l₂). The integrals depend on complex parameters z and μ. We show that I_a,b(z,μ;m₁,m₂,l₁,l₂) equals J_a,b(e^μ,z;l₁,l₂,m₁,m₂) up to an explicit factor, thus establishing an equality of l₂-dimensional q-hypergeometric and m₂-dimensional hypergeometric integrals. The identity is based on the duality for the qKZ and dynamical difference equations.