集合上的递归函数

本文在Ｊｅｎｓｅｎ和Ｋａｒｐ工作的基础上引进了集合上的递归函数的概念．研究了递归集函数的初步性质，讨论了递归集函数与Ｊｅｎｓｅｎ和Ｋａｒｐ定义的原始递归集函数及递归数论函数之间的关系，并给出了ＺＦＣ的可定义集模型上递归集函数的范式定理．     

I.I.D. STATISTICAL CONTRACTION OPERATORS AND STATISTICALLY SELF－SIMILAR SETS

I.i.d. random sequence is the simplest but very basic one in stochastic processes, and statistically self-similar set is the simplest but very basic one in random recursive sets in the theory of random fractal. Is there any relation between i.i.d. random sequence and statistically self-similar set? This paper gives a basic theorem which tells us that the random recursive set generated by a collection of i.i.d. statistical contraction operators is always a statistically self-similar set.     

Isomorphism of the Index Sets of Discrete Families of General Recursive Functions

We establish isomorphism between the index set of an arbitrary computable family of general recursive functions and the index set of a certain computable discrete family of general recursive functions.     

Domains of t-Functions

A nonempty and nonconstant partial recursive function such that any function resembling it is recursively isomorphic to it is called a t-function. It is proved that the domain of any t-function is neither a simple nor a pseudosimple set.     

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.     

A construction of interpolating wavelets on invariant sets

We introduce the concept of a refinable set relative to a family of contractive mappings on a metric space, and demonstrate how such sets are useful to recursively construct interpolants which have a multiscale structure. The notion of a refinable set parallels that of a refinable function, which is the basis of wavelet construction. The interpolation points we recursively generate from a refinable set by a set-theoretic multiresolution are analogous to multiresolution for functions used in wavelet construction. We then use this recursive structure for the points to construct multiscale interpolants. Several concrete examples of refinable sets which can be used for generating interpolatory wavelets are included.

     

Maximal independent sets on a grid graph

An independent vertex set of a graph is a set of vertices of the graph in which no two vertices are adjacent, and a maximal independent set is one that is not a proper subset of any other independent set. In this paper we count the number of maximal independent sets of vertices on a complete rectangular grid graph. More precisely, we provide a recursive matrix-relation producing the partition function with respect to the number of vertices. The asymptotic behavior of the maximal hard square entropy constant is also provided. We adapt the state matrix recursion algorithm, recently invented by the author to answer various two-dimensional regular lattice model problems in enumerative combinatorics and statistical mechanics.     

A cohesive set which is not high

We study the degrees of unsolvability of sets which are cohesive (or have weaker recursion-theoretic “smallness” properties). We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r-cohesive sets, and we show that the degrees of r-cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets in place of r-cohesive and cohesive sets, respectively. We show that every strongly hyperimmune set whose degree contains either a Boolean combination of ∑2 sets or a 1-generic set is of high degree. We also study primitive recursive analogues of these notions and in this case we characterize the corresponding degrees exactly. MSC: 03D30, 03D55.     

Further results on large set of disjoint pure Mendelsohn triple systems

In this article, we study a large set of disjoint pure Mendelsohn triple systems “with holes” (briefly LPHMTS), which is a generalization of large set of disjoint pure Mendelsohn triple systems (briefly LPMTS), and give some recursive constructions on LPHMTS. Using these constructions, we show that there exists LPMTS(2ⁿ + 2) for any n ≠ 2. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 274–290, 2000     

几乎差集偶的分圆构造

本文研究了几乎差集偶的构造问题.利用分圆方法构造几乎差集偶,获得几乎差集偶的若干性质和一些几乎差集偶的类.     

Factors of Functions,AC and Recursive Analogues

We investigate certain statements about factors of unary functions (in particular,factors of permutations) which have connections with weak forms of the axiom of choice. We discuss more extensively the fine structure of Howard and Rubin's Form 314 (which concerns bireflectivity of permutations) from [4]. Some of our set‐theoretic results have also interesting recursive versions.     

Relative difference sets in semidirect products with an amalgamated subgroup

We call a group G with subgroups G₁, G₂ such that G = G₁G₂ and both N = G₁ ∩ G₂ and G₁ are normal in G a semidirect product with amalgamated subgroup N. We show that if G_l is a group with N_l ? G_l containing a relative ‐difference set relative to N_l for l = 1,2, and if there exists a “compatible coupling” from (G₂, N₂) to (G₁, N₁), a notion introduced in the paper, then for any i,j ∈ ? there exists at least one semidirect product with amalgamated subgroup N ? N₁ ? N₂ containing a relative ‐difference set. We say “at least one” to emphasize that the proof is via recursive construction and that different groups may be obtained depending on the choices made at different stages of the recursion. A special case of this result shows that if K is any finite group containing a normal relative ‐difference set, then there exists, for each i ∈ ?, at least one semidirect product with amalgamated subgroup N containing a relative ‐difference set. These results suggest that the class of semidirect products with an amalgamated subgroup provides a rich source of new (non‐abelian) semiregular relative difference sets. © 2004 Wiley Periodicals, Inc.     

Computably Rigid Models with Enumerable Submodels

We consider recursive representations for the set of rational numbers with a distinguished dense and codense subset and for some Boolean algebras with a distinguished subalgebra. We show that the rejection of recursiveness of the distinguished submodel opens up the possibility of constructing models without nontrivial automorphisms. The proof is carried out by the priority method.     

A Diller-Nahm-style functional interpretation of $\hbox{\sf KP} \omega$

The Dialectica-style functional interpretation of Kripke-Platek set theory with infinity () given in [1] uses a choice functional (which is not a definable set function of (). By means of a Diller-Nahm-style interpretation (cf. [4]) it is possible to eliminate the choice functional and give an interpretation by set functionals primitive recursive in . This yields the following characterization: The class of -definable set functions of coincides with the collection of set functionals of type 1 primitive recursive in . Received: 26 August 1998     

Constructions of External Difference Families and Disjoint Difference Families

External difference families (EDFs) are a type of new combinatorial designs originated from cryptography. In this paper, some earlier ideas of recursive and cyclotomic constructions of combinatorial designs are extended, and a number of classes of EDFs and disjoint difference families are presented. A link between a subclass of EDFs and a special type of (almost) difference sets is set up.     

Unisolvency for multivariate polynomial interpolation in Coatmèlec configurations of nodes

A new and straightforward proof of the unisolvability of the problem of multivariate polynomial interpolation based on Coatmèlec configurations of nodes, a class of properly posed set of nodes defined by hyperplanes, is presented. The proof generalizes a previous one for the bivariate case and is based on a recursive reduction of the problem to simpler ones following the so-called Radon-Bézout process.     

程度下近似算子与变精度上近似算子的差运算模型

目的是探讨精度与程度的复合,建立并研究新的粗糙集拓展模型.基于程度与精度的逻辑差需求,提出了程度下近似算子与变精度上近似算子的差运算模型,得到了程度下近似算子与变精度上近似算子的差运算的宏观本质、精确描述与基本性质.并用一个医疗实例说明了模型的意义和应用.程度下近似算子与变精度上近似算子的差运算模型,部分的拓展了程度粗糙集模型和经典粗糙集模型.     

Almost semirecursive sets

LetA be a subset of , and leta∉A. The setA is said to be almost semirecursive, if there is a two-place general recursive functionf such thatf(x, y)ε{x, y, a}∧({x, y}⊆A⇌f(x, y)εA) for all . Among other facts, it is proved that ifA and are almost semirecursive sets, thenA is a semirecursive set, and that there exists a wsr^*-set that is neither a wsr-nor an almost semirecursive set. Translated fromMatematicheskie Zametki, Vol. 66, No. 2, pp. 188–193, August, 1999.     

Solution of Fredholm Equations with Symmetric Difference Kernels

A simple numerical procedure is outlined for the solution ofFredholm equations with symmetric difference kernels. By retainingthe properties of symmetry and convolution in the approximatingdiscrete system we obtain a set of equations identical in formto the normal equations arising in the prediction of stationarytime series. A standard recursive method allows us to work withlarge systems of equations, the resulting fineness of the meshpermitting accurate solutions. An alternative method of solvingthe same normal equations is based on the Wiener-Hopf procedureand may be more efficient than the recursive method for verylarge systems.     

MULTIFRACTAL DECOMPOSITION OF CERTAIN RECURSIVE SETS WITHOUT THE OPEN SET CONDITION

1 IntroductionMultifractal decomposition has been investigated by rnany authors, it has become a use-ful tool in the fractal allalysis. Cawley and Mauldin had given good results on Moran fractaldecomPosition[3], Edgar and Mauldin studied the degraph multifractals[4], Falconer random-nized Cawley's results and the latest results on random selfsidrilar multifractals were doneby Arbeiter and Patzschke under rather weak .o1ldition.I2J. However, all these results wereestablished on certain sepa…