Effective Structures

The connection between some special properties of the computable functions in an abstract structure and the existence of a recursive and semi-recursive representation of the structure is studied. The considerations are based on the notion of computability on many-sorted abstract structures.     

On induced and isometric embeddings of graphs into the strong product of paths

The strong isometric dimension and the adjacent isometric dimension of graphs are compared. The concepts are equivalent for graphs of diameter 2 in which case the problem of determining these dimensions can be reduced to a covering problem with complete bipartite graphs. Using this approach several exact strong and adjacent dimensions are computed (for instance of the Petersen graph) and a positive answer is given to the Problem 4.1 of Fitzpatrick and Nowakowski [The strong isometric dimension of finite reflexive graphs, Discuss. Math. Graph Theory 20 (2000) 23-38] whether there is a graph G with the strong isometric dimension bigger that ⌈|V(G)|/2⌉.     

P-析取强P-反演半群

介绍了强P-反演半群的概念,刻划了P-析取强P-反演半群的某些特征.     

Pointwise strong and very strong approximation of Fourier series

We present an estimation of the and H _u ^λφ f means as approximation versions of the Totik type generalization (see [6, 7]) of the result of G. H. Hardy, J. E. Littlewood, considered by N. L. Pachulia in [5]. Some results on the norm approximation will also be given.      

Bounded Immunity and Btt-Reductions

We define and study a new notion called k-immunity that lies between immunity and hyperimmunity in strength. Our interest in k-immunity is justified by the result that θ does not k-tt reduce to a k-immune set, which improves a previous result by Kobzev [7]. We apply the result to show that Φ′ does not btt-reduce to MIN, the set of minimal programs. Other applications include the set of Kolmogorov random strings, and retraceable and regressive sets. We also give a new characterization of effectively simple sets and show that simple sets are not btt-cuppable.     

Space complexity of Abelian groups

We develop a theory of LOGSPACE structures and apply it to construct a number of examples of Abelian Groups which have LOGSPACE presentations. We show that all computable torsion Abelian groups have LOGSPACE presentations and we show that the groups , and the additive group of the rationals have LOGSPACE presentations over a standard universe such as the tally representation and the binary representation of the natural numbers. We also study the effective categoricity of such groups. For example, we give conditions are given under which two isomorphic LOGSPACE structures will have a linear space isomorphism.      

Sufficient conditions for a control to be a strong minimum

The control literature either presents sufficient conditions for global optimality (for example, the Hamilton-Jacobi-Bellman theorem) or, if concerned with local optimality, restricts attention to comparison controls which are local in theL -sense. In this paper, use is made of an exact expression for the change in cost due to a change in control, a natural extension of a result due to Weierstrass, to obtain sufficient conditions for a control to be a strong minimum (in the sense that comparison controls are merely required to be close in theL ₁-sense).     

Structure of free strong doppelsemigroups

We consider strong doppelsemigroups which are sets with two binary associative operations satisfying axioms of strong interassociativity. Commutative dimonoids in the sense of Loday are examples of strong doppelsemigroups and two strongly interassociative semigroups give rise to a strong doppelsemigroup. The main aim of this paper is to construct a free strong doppelsemigroup, a free n-dinilpotent strong doppelsemigroup, a free commutative strong doppelsemigroup and a free n-nilpotent strong doppelsemigroup. We also characterize the least n-dinilpotent congruence, the least commutative congruence, the least n-nilpotent congruence on a free strong doppelsemigroup and establish that the automorphism group of every constructed free algebra is isomorphic to the symmetric group.     

Dense computability structures

We examine computability structures on a metric space and the relationships between maximal, separable and dense computability structures. We prove that in a computable metric space which has the effective covering property and compact closed balls for a given computable sequence which is a metric basis there exists a unique maximal computability structure which contains that sequence. Furthermore, we prove that each maximal computability structure on a convex subspace of Euclidean space is dense. We also examine subspaces of Euclidean space on which each dense maximal computability structure is separable and prove that spheres, boundaries of simplices and conics are such spaces.     

The canonical Ramsey theorem and computability theory

Using the tools of computability theory and reverse mathematics, we study the complexity of two partition theorems, the Canonical Ramsey Theorem of Erdös and Rado, and the Regressive Function Theorem of Kanamori and McAloon. Our main aim is to analyze the complexity of the solutions to computable instances of these problems in terms of the Turing degrees and the arithmetical hierarchy. We succeed in giving a sharp characterization for the Canonical Ramsey Theorem for exponent 2 and for the Regressive Function Theorem for all exponents. These results rely heavily on a new, purely inductive, proof of the Canonical Ramsey Theorem. This study also unearths some interesting relationships between these two partition theorems, Ramsey's Theorem, and König's Lemma.

     

Regime-switching diffusion processes: strong solutions and strong Feller property

Abstract

We investigate the existence and uniqueness of strong solutions for state-dependent regime-switching diffusion processes in an infinite state space with singular coefficients. Non-explosion conditions are given by using the Zvonkin’s transformation. The strong Feller property is proved by further assuming that the diffusion in each fixed environment generates a strong Feller semigroup, and our results can also be applied to irregular or degenerate situations.     

On strongly almost trivial embeddings of graphs

We present four new classes of graphs, two of which every member has a strongly almost trivial embedding, and the other two of which every member has no strongly almost trivial embeddings. We show that the property that a graph has a strongly almost trivial embedding and the property that a graph has no strongly almost trivial embeddings are not inherited by minors. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

Cover-preserving order embeddings into Boolean lattices

It is not known which finite graphs occur as induced subgraphs of a hypercube. This is relevant in the theory of parallel computing. The ordered version of the problem is: Which finite posets P occur as cover-preserving subposets of a Boolean lattice? Our main Theorem gives (for 0,1-posets) a necessary and sufficient condition, which involves the chromatic number of a graph associated to P. It is applied respectively to upper balanced, meet extremal, meet semidistributive, and semidistributive lattices P. More specifically, we consider isometric embeddings of posets into Boolean lattices. In particular, answering a question of Ivan Rival to the positive, a nontrivial invariant for the covering graph of a poset is found.     

Semi‐strong and strong solutions for variable density asymmetric fluids in unbounded domains

We establish the existence of local in time semi‐strong solutions and global in time strong solutions for the system of equations describing flows of viscous and incompressible asymmetric fluids with variable density in general three‐dimensional domains with boundary uniformly of class C³. Under suitable assumptions, uniqueness of local semi‐strong solutions is also proved. Copyright © 2016 John Wiley & Sons, Ltd.     

Lower and upper orientable strong radius and strong diameter of complete k-partite graphs

For two vertices u and v in a strong digraph D, the strong distance sd(u,v) between u and v is the minimum size (the number of arcs) of a strong sub-digraph of D containing u and v. For a vertex v of D, the strong eccentricity se(v) is the strong distance between v and a vertex farthest from v. The strong radius srad(D) (resp. strong diameter sdiam(D)) is the minimum (resp. maximum) strong eccentricity among the vertices of D. The lower (resp. upper) orientable strong radius srad(G) (resp. SRAD(G)) of a graph G is the minimum (resp. maximum) strong radius over all strong orientations of G. The lower (resp. upper) orientable strong diameter sdiam(G) (resp. SDIAM(G)) of a graph G is the minimum (resp. maximum) strong diameter over all strong orientations of G. In this paper, we determine the lower orientable strong radius and diameter of complete k-partite graphs, and give the upper orientable strong diameter and the bounds on the upper orientable strong radius of complete k-partite graphs. We also find an error about the lower orientable strong diameter of complete bipartite graph K_m,n given in [Y.-L. Lai, F.-H. Chiang, C.-H. Lin, T.-C. Yu, Strong distance of complete bipartite graphs, The 19th Workshop on Combinatorial Mathematics and Computation Theory, 2002, pp. 12-16], and give a rigorous proof of a revised conclusion about sdiam(K_m,n).     

Hamiltonian decompositions of strong products

It is shown that if both G₁ and G₂ are Hamiltonian decomposable, then so is their strong product. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 45–55, 1998     

The computational strength of matchings in countable graphs

In a 1977 paper, Steffens identified an elegant criterion for determining when a countable graph has a perfect matching. In this paper, we will investigate the proof-theoretic strength of this result and related theorems. We show that a number of natural variants of these theorems are equivalent, or closely related, to the “big five” subsystems of reverse mathematics.The results of this paper explore the relationship between graph theory and logic by showing the way in which specific changes to a single graph-theoretic principle impact the corresponding proof-theoretic strength. Taken together, the results and questions of this paper suggest that the existence of matchings in countable graphs provides a rich context for understanding reverse mathematics more broadly.     

On complete convergence for strong mixing sequences

In this paper, some results on complete convergence for strong mixing sequences are presented under some suitable conditions. A Marcinkiewicz–Zygmund-type strong law of large numbers is also obtained.