On maximal subalgebras of the algebras of unary recursive functions

Under consideration are the algebras of unary functions with supports in countable primitively recursively closed classes and composition operation. Each algebra of this type is proved to have continuum many maximal subalgebras including the set of all unary functions of the class ε ² of the Grzegorczyk hierarchy.     

The closure operator in a multivalued logic based on functional equations

An operator of FE-closure is introduced on the set of functions of a multivalued logic based on the systems of functional equations. It is proved that, for every k ≥ 2, the FE-closure operator generates a finite classification on the set P _k of functions of k-valued logic. The least class in this classification is shown to be the class H _k of all homogeneous functions. Also a series of corollaries are obtained concerning the finite FE-generating sets in the FE-closed classes.     

Maximal clones on uncountable sets that include all permutations

We first determine the maximal clones on a set X of infinite regular cardinality κ which contain all permutations but not all unary functions, extending a result of Heindorf’s for countably infinite X. If κ is countably infinite or weakly compact, this yields a list of all maximal clones containing the permutations, since in that case the maximal clones above the unary functions are known. We then generalize a result of Gavrilov’s to obtain on all infinite X a list of all maximal submonoids of the monoid of unary functions which contain the permutations. Received January 8, 2004; accepted in final form December 22, 2004.     

Approximation Algorithms for Dispersion Problems

Given a collection of weighted sets, each containing at most k elements drawn from a finite base set, the k-set packing problem is to find a maximum weight sub-collection of disjoint sets. A greedy algorithm for this problem approximates it to within a factor of k, and a natural local search has been shown to approximate it to within a factor of roughly k − 1. However, neither paradigm can yield approximations that improve on this.We present an approximation algorithm for the weighted k-set packing problem that combines the two paradigms by starting with an initial greedy solution and then repeatedly choosing the best possible local improvement. The algorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotically tight. This is the first asymptotic improvement over the straightforward ratio of k.     

FE classification of functions of many-valued logic

On the set of functions of many-valued logic, we consider the closure operator defined on the basis of systems of functional equations (the operator of FE closure). This operator generates an FE classification of the functions of many-valued logic, whose kernel consists of classes of S _G -type defined by groups of permutations of G. A number of results are obtained to guarantee FE precompleteness of classes of only this type in the classes of S _G type. The results obtained are illustrated by examples of functions of 2-, 3-, and 4-valued logics.     

A small generating set for the 3‐BD closed set of block sizes ≥ 6

Let v, k be positive integers and k ≥ 3, then K_k = : {v: v ≥ k} is a 3‐BD closed set. Two finite generating sets of 3‐BD closed sets K₄ and K₅ are obtained by H. Hanani [5] and Qiurong Wu [12] respectively. In this article we show that if v ≥ 6, then v ∈ B₃(K,1), where K = {6,7,…,41,45,46,47,51,52,53,83,84}\{22,26}; that is, we show that K is a generating set for K₆. Finally we show that v ∈ B₃(6,20) for all v ∈ K\{35,39,40,45}. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 128–136, 2008     

Algebraic axiomatization of tense intuitionistic logic

We introduce two unary operators G and H on a relatively pseudocomplemented lattice which form an algebraic axiomatization of the tense quantifiers “it is always going to be the case that” and “it has always been the case that”. Their axiomatization is an extended version for the classical logic and it is in accordance with these operators on many-valued Łukasiewicz logic. Finally, we get a general construction of these tense operators on complete relatively pseudocomplemented lattice which is a power lattice via the so-called frame.     

Cyclic Relative Difference Sets and their p-Ranks

By modifying the constructions in Helleseth et al. [10] and No [15], we construct a family of cyclic ((q ^3k –1)/(q–1), q–1, q ^3k–1, q ^3k–2) relative difference sets, where q=3 ^e . These relative difference sets are liftings of the difference sets constructed in Helleseth et al. [10] and No [15]. In order to demonstrate that these relative difference sets are in general new, we compute p-ranks of the classical relative difference sets and 3-ranks of the newly constructed relative difference sets when q=3. By rank comparison, we show that the newly constructed relative difference sets are never equivalent to the classical relative difference sets, and are in general inequivalent to the affine GMW difference sets.     

Finding independent sets in a graph using continuous multivariable polynomial formulations

Two continuous formulations of the maximum independent set problem on a graph G=(V,E) are considered. Both cases involve the maximization of an n-variable polynomial over the n-dimensional hypercube, where n is the number of nodes in G. Two (polynomial) objective functions F(x) and H(x) are considered. Given any solution to x ₀ in the hypercube, we propose two polynomial-time algorithms based on these formulations, for finding maximal independent sets with cardinality greater than or equal to F(x₀) and H(x₀), respectively. A relation between the two approaches is studied and a more general statement for dominating sets is proved. Results of preliminary computational experiments for some of the DIMACS clique benchmark graphs are presented.     

Dynamic Globally Concavized Filled Function Method for Continuous Global Optimization

We consider a box-constrained continuous global minimization problem. A new definition of filled function, namely that of globally concavized filled function, is proposed. A new two-parameter class of globally concavized filled functions A(x,k,p) is constructed, which has the same global minimizers as the problem on the solution domain if p is large enough. The minimization of A(x,k,p) can escape successfully from a previously converged local minimizer by taking increasing values of k. A dynamic globally concavized filled function method is designed based on these functions and the convergence property is proved. Numerical experiments on a set of standard testing functions show that the resulting method is competitive with some well-known global minimization methods. This research was supported partially by the NSFC under Grants 60773126 and 10301009, the NKBRSF of China under Grant 2006CB805900, and the Natural Science Foundation of Fujian province under Grant 2006J0030.     

Cardinality of the Set of Delta–Closed Classes of Functions of Multi–Valued Logic

A closure under composition operation and weak version of inversion operation is considered on the set of functions of k–valued logic. The cardinality of the set of all such closed classes is calculated.     

Positively closed classes of three-valued logic

We state some theoretical prerequisites and indicate approaches to constructing a positive classification of the set of functions of k-valued logic. Basing on this, we find all 194 positively closed classes of three-valued logic. We describe them using the semigroups of endomorphisms and indicating positive bases.     

Maximal sets of non-polar points of quadrics and symplectic polarities over GF(2)

A cap on a non-singular quadric over GF(2) is a set of points that are pairwise non-polar; equivalently the join of any two of the points is a chord. A non-secant set of the quadric is a set of points off the quadric that are pairwise non-polar; equivalently the join of any two of the points is skew to the quadric. We determine all the maximal caps and all the maximal non-secant sets of all non-singular quadrics over GF(2); and also all the maximal sets of non-polar points for symplectic polarities over GF(2). The classification is in terms of caps of greatest size on elliptic quadrics Q _– ^8k+3 (2), hyperbolic quadrics Q ₊ ^8k+7 (2) and on quadrics Q _4k+2(2), and of non-secant sets of greatest size of Q _– ^8k+1 (2), Q ₊ ^8k+5 (2) and Q _4k (2), for all quadrics of these types that occur as sections of the parent quadric or belong to the symplectic polarity. The sets of greatest size for these types of quadrics are larger than for other types. The results have implications about the non-existence of ovoids and the exterior sets of Thas. Only one part of the simple geometric inductive argument extends to larger ground fields.     

Alliance free and alliance cover sets

A defensive (offensive) k-alliance in Γ = (V,E) is a set S ⊆ V such that every υ in S (in the boundary of S) has at least k more neighbors in S than it has in V / S. A set X ⊆ V is defensive (offensive) k-alliance free, if for all defensive (offensive) k-alliance S, S/X ≠ ∅, i.e., X does not contain any defensive (offensive) k-alliance as a subset. A set Y ⊆ V is a defensive (offensive) k-alliance cover, if for all defensive (offensive) k-alliance S, S ∩ Y ≠ ∅, i.e., Y contains at least one vertex from each defensive (offensive) k-alliance of Γ. In this paper we show several mathematical properties of defensive (offensive) k-alliance free sets and defensive (offensive) k-alliance cover sets, including tight bounds on their cardinality.     

A common generalization of line graphs and clique graphs

Both the line graph and the clique graph are defined as intersection graphs of certain families of complete subgraphs of a graph. We generalize this concept. By a k-edge of a graph we mean a complete subgraph with k vertices or a clique with fewer than k vertices. The k-edge graph Δ_k(G) of a graph G is defined as the intersection graph of the set of all k-edges of G. The following three problems are investigated for k-edge graphs. The first is the characterization problem. Second, sets of graphs closed under the k-edge graph operator are found. The third problem is the question of convergence: What happens to a graph if we take iterated k-edge graphs?     

Invariant curves of one-step methods

This paper considers the invariant sets of numerical one-step integration methods in a neighbourhood of a hyperbolic periodic solution of a nonlinear ODE. Using results from the dynamical systems theory it was possible to show that for the usual one-step methods the invariant sets areC ^k-circles (closed curves) for small enough stepsizeh. Here we give a direct proof for that and also show that they areO(h ^p)C ^k-close to the true periodic trajectory, wherep is the order of the method.Most of this work was done during the author's visit at the Mittag-Leffler Institute, Djursholm, Sweden, academic year 1985–86.     

On Partial Classes Containig All Monotone and Zero-Preserving Total Boolean Functions

We describe sets of partial Boolean functions being closed under the operations of superposition. For any class A of total functions we define the set ??(A) consisting of all partial classes which contain precisely the functions of A as total functions. The cardinalities of such sets ??(A) can be finite or infinite. We state some general results on ??(A). In particular, we describe all 30 closed sets of partial Boolean functions which contain all monotone and zero-preserving total Boolean functions.     

p -Sparse BEM for weakly singular integral equation with random data

We consider the weakly singular boundary integral equation 𝒱u = g on a randomly perturbed smooth closed surface Γ(ω) with deterministic g or on a deterministic closed surface Γ with stochastic g (ω). The aim is the computation of the centered moments ℳ︁^k u, k ⩾ 1, if the corresponding moments of the perturbation are known. The problem on the stochastic surface is reduced to a problem on the nominal deterministic surface Γ with the random perturbation parameter κ (ω). Resulting formulation for the k th moment is posed in the tensor product Sobolev spaces and involve the k -fold tensor product operators. The standard full tensor product Galerkin BEM requires 𝒪(N^k) unknowns for the k th moment problem, where N is the number of unknowns needed to discretize the nominal surface Γ. Based on [1], we develop the p -sparse grid Galerkin BEM to reduce the number of unknowns to 𝒪(N (log N)^{k –1}) (cf. [2], [3] for the wavelet approach). (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Some Solved and Unsolved Remainder Equations

The remainder set A?B of a set of sentences A modulo a set of sentences B is the set of all maximal subsets of A not implying any element of B. A remainder equation is an expression containing remainder sets, such as {A} = B?X, in which at least one set is unknown. Solutions to some classes of remainder equations are reported, and some unsolved problems are listed.