Computability of Minimizers and Separating Hyperplanes

We prove in recursive analysis an existence theorem for computable minimizers of convex computable continuous real-valued functions, and a computable separation theorem for convex sets in ?^m. Mathematics Subject Classification: 03F60, 52A40.     

图的笛卡儿积的测地数

对于图G内的任意两点u和v，u-v测地线是指u和v之间的最短路．I（u，v）表示位于u-v测地线上所有点的集合，对于．S∈V（G），I（S）表示所有I（u，v）的并，这里“u,v∈．S．G的测地数g（G）是使I（S）=V（G）的点集．S的最小基数．在这篇文章，我们研究G×K3的测地数和g（G）与g（G×K3）相等的充分必要条件，还给出了T×Km和Cn×Km的测地数，这里T是树．     

Category Theoretic Properties of Topological Structures and Proximity Structures on L-fuzzy Space

This paper formulates the category of L-fuzzy spaces and fuzzy functions. It shows that the category of topological spaces and continuous fuzzy functions is a direct generalization of TOP and LTOP Moreover, it defines the concept of proximity space on L-fuzzy space and introduces its fundamental properties. A comparison between the classical case and the ordinary case has been outlined.     

Computability of Self-Similar Sets

We investigate computability of a self-similar set on a Euclidean space. A nonempty compact subset of a Euclidean space is called a self-similar set if it equals to the union of the images of itself by some set of contractions. The main result in this paper is that if all of the contractions are computable, then the self-similar set is a recursive compact set. A further result on the case that the self-similar set forms a curve is also discussed.     

Turing degrees of nonabelian groups

For a countable structure , the (Turing) degree spectrum of is the set of all Turing degrees of its isomorphic copies. If the degree spectrum of has the least degree , then we say that is the (Turing) degree of the isomorphism type of . So far, degrees of the isomorphism types have been studied for abelian and metabelian groups. Here, we focus on highly nonabelian groups. We show that there are various centerless groups whose isomorphism types have arbitrary Turing degrees. We also show that there are various centerless groups whose isomorphism types do not have Turing degrees.

     

Computability Over Structures of Infinite Signature

Continuing the paper [7], in which the Blum-Shub-Smale approach to computability over the reals has been generalized to arbitrary algebraic structures, this paper deals with computability and recognizability over structures of infinite signature. It begins with discussing related properties of the linear and scalar real structures and of their discrete counterparts over the natural numbers. Then the existence of universal functions is shown to be equivalent to the effective encodability of the underlying structure. Such structures even have universal functions satisfying the s-m-n theorem and related features. The real and discrete examples are discussed with respect to effective encodability. Megiddo structures and computational extensions of effectively encodable structures are encodable, too. As further variants of universality, universal functions with enumerable sets of program codes and such ones with constructible codes are investigated. Finally, the existence of m-complete sets is shown to be independent of the effective encodability of structures, and the linear and scalar structures are discussed once more, under this aspect.     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

On the geodetic number and related metric sets in Cartesian product graphs

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in at least one interval between the vertices of S. The size of a minimum geodetic set in G is the geodetic number of G. Upper bounds for the geodetic number of Cartesian product graphs are proved and for several classes exact values are obtained. It is proved that many metrically defined sets in Cartesian products have product structure and that the contour set of a Cartesian product is geodetic if and only if their projections are geodetic sets in factors.     

近似空间的拓扑性质及其应用

近似空间(U,R)的全体可定义集构成X上的一个拓扑.本文在不要求论域U是有限的前提下探讨近似空间上这个拓扑的局部性质和可数性质,以及拓扑空间可近似化的充要条件及公理化体系,并寻找它们在粗糙集理论中的应用.     

On the Total Domination Number of Cartesian Products of Graphs

The most famous open problem involving domination in graphs is Vizings conjecture which states the domination number of the Cartesian product of any two graphs is at least as large as the product of their domination numbers. In this paper, we investigate a similar problem for total domination. In particular, we prove that the product of the total domination numbers of any nontrivial tree and any graph without isolated vertices is at most twice the total domination number of their Cartesian product, and we characterize the extremal graphs.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal     

Quasimaximality and principal filters isomorphism between

Let I be a quasimaximal subset of a computable basis of the fully efective vector space V . We give a necessary and sufficient condition for the existence of an isomorphism between the principal filter respectivelly. We construct both quasimaximal sets that satisfy and quasimaximal sets that do not satisfy this condition. With the latter we obtain a negative answer to Question 5.4 posed by Downey and Remmel in [3].Based on the authors Ph.D. dissertation.Mathematics Subject Classification (2000): 03D25, 03C57     

Weakly Convex Sets and Their Properties

In this paper, the notion of a weakly convex set is introduced. Sharp estimates for the weak convexity constants of the sum and difference of such sets are given. It is proved that, in Hilbert space, the smoothness of a set is equivalent to the weak convexity of the set and its complement. Here, by definition, the smoothness of a set means that the field of unit outward normal vectors is defined on the boundary of the set; this vector field satisfies the Lipschitz condition. We obtain the minimax theorem for a class of problems with smooth Lebesgue sets of the goal function and strongly convex constraints. As an application of the results obtained, we prove the alternative theorem for program strategies in a linear differential quality game.     

Computability of String Functions Over Algebraic Structures Armin Hemmerling

We present a model of computation for string functions over single-sorted, total algebraic structures and study some basic features of a general theory of computability within this framework. Our concept generalizes the Blum-Shub-Smale setting of computability over the reals and other rings. By dealing with strings of arbitrary length instead of tuples of fixed length, some suppositions of deeper results within former approaches to generalized recursion theory become superfluous. Moreover, this gives the basis for introducing computational complexity in a BSS-like manner. Relationships both to classical computability and to Friedman's concept of eds computability are established. Two kinds of nondeterminism as well as several variants of recognizability are investigated with respect to interdependencies on each other and on properties of the underlying structures. For structures of finite signatures, there are universal programs with the usual characteristics. For the general case of not necessarily finite signature, this subject will be studied in a separate, forthcoming paper.     

论袋映射及其结构

本文论述了袋映射的缘起，给出了袋映射的对称函数列表示法，并在此基础上证明了Ｖａｌｕｅｆｕｎｃｔｉｏｎａｌ的袋映射可用一个一元函数和一个二元对称函数来表达，从而进一步明确了这类袋映射的构造。     

On the complexity of categoricity in computable structures

We investigate the computational complexity the class of Γ‐categorical computable structures. We show that hyperarithmetic categoricity is Π¹₁‐complete, while computable categoricity is Π⁰₄‐hard. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Several Special Complex Structures and Their Deformation Properties

We introduce a natural map from the space of pure-type complex differential forms on a complex manifold to the corresponding one on the infinitesimal deformations of this complex manifold. By use of this map, we generalize an extension formula in a recent work of K. Liu, X. Yang, and the first author. As direct corollaries, we prove several deformation invariance theorems for Hodge numbers. Moreover, we also study the Gauduchon cone and its relation with the balanced cone in the Kähler case, and show that the limit of the Gauduchon cone in the sense of D. Popovici for a generic fiber in a Kählerian family is contained in the closure of the Gauduchon cone for this fiber.     

Computability of measurable sets via effective topologies

We investigate in the frame of TTE the computability of functions of the measurable sets from an infinite computable measure space such as the measure and the four kinds of set operations. We first present a series of undecidability and incomputability results about measurable sets. Then we construct several examples of computable topological spaces from the abstract infinite computable measure space, and analyze the computability of the considered functions via respectively each of the standard representations of the computable topological spaces constructed. The authors are supported by grants of NSFC and DFG.     

Computability of measurable sets via effective metrics

We consider how to represent the measurable sets in an infinite measure space. We use sequences of simple measurable sets converging under metrics to represent general measurable sets. Then we study the computability of the measure and the set operators of measurable sets with respect to such representations. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Cartesian Closed Topological Categories and Tensor Products

The projective tensor product in a category of topological R-modules (where R is a topological ring) can be defined in Top, the category of topological spaces, by the same universal property used to define the tensor product of R-modules in Set. In this article, we extend this definition to an arbitrary topological category X and study how the Cartesian closedness of X is related to the monoidal closedness of the category of R-module objects in X. Mathematics Subject Classifications (2000) 18D15, 18D35, 18A40.