Reflection-closed varieties of multisorted algebras and minor identities

The notion of reflection is considered in the setting of multisorted algebras. The Galois connection induced by the satisfaction relation between multisorted algebras and minor identities provides a characterization of reflection-closed varieties: a variety of multisorted algebras is reflection-closed if and only if it is definable by minor identities. Minor-equational theories of multisorted algebras are described by explicit closure conditions. It is also observed that nontrivial varieties of multisorted algebras of a non-composable type are reflection-closed.     

Calculus of Generalized Quasi-differentiable Functions I: Some Results on the Space of Pairs of Convex-Set Collections

A Riesz space K1 whose elements are pairs of convex-set collections is presented for the study on the calculus of generalized quasi-differentiable functions. The space K1 is constructed by introducing a well-defined equivalence relation among pairs of collections of convex sets. Some important properties on the norm and operations in K1 are given.     

Galois theory for semiclones

We present a Galois theory connecting finitary operations with pairs of finitary relations, one of which is contained in the other. The Galois closed sets on both sides are characterised as locally closed subuniverses of the full iterative function algebra (semiclones) and relation pair clones, respectively. Moreover, we describe the modified closure operators if only functions and relation pairs of a certain bounded arity, respectively, are considered.     

Forbidden minors to graphs with small feedback sets

Finite obstruction set characterizations for lower ideals in the minor order are guaranteed to exist by the graph minor theorem. In this paper we characterize several families of graphs with small feedback sets, namely k₁-F V S , k₂-F E S and (k₁,k₂)-F V /E S , for small integer parameters k₁ and k₂. Our constructive methods can compute obstruction sets for any minor-closed family of graphs, provided the pathwidth (or treewidth) of the largest obstruction is known.     

Some open problems on excluding a uniform matroid

It would appear that minor-closed classes of matroids that are representable over any given finite field are very well behaved. This paper explores what happens when we go a little further to minor-closed classes of matroids that exclude a uniform minor. Numerous open problems of varying difficulty are posed.     

Multisorted dualisability: change of base

We prove that if a quasivariety A{\mathcal{A}} generated by a finite family M{\mathcal{M}} of finite algebras has a multisorted duality based on M{\mathcal{M}}, then A{\mathcal{A}} has a multisorted duality based on any finite family of finite algebras that generates it.     

On the matroids in which all hyperplanes are binary

In this paper, it is shown that, for a minor-closed class of matroids, the class of matroids in which every hyperplane is in is itself minor-closed and has, as its excluded minors, the matroids U_1.1 N such that N is an excluded minor for . This result is applied to the class of matroids of the title, and several alternative characterizations of the last class are given.     

A finitely axiomatizable undecidable equational theory with recursively solvable word problems

In this paper we construct a finitely based variety, whose equational theory is undecidable, yet whose word problems are recursively solvable, which solves a problem stated by G. McNulty (1992). The construction produces a discriminator variety with the aforementioned properties starting from a class of structures in some multisorted language (which may include relations), axiomatized by a finite set of universal sentences in the given multisorted signature. This result also presents a common generalization of the earlier results obtained by B. Wells (1982) and A. Mekler, E. Nelson, and S. Shelah (1993).

     

Excluded-Minor Characterization of Apex-Outerplanar Graphs

The class of outerplanar graphs is minor-closed and can be characterized by two excluded minors: \(K_4\) and \(K_{2,3}\). The class of graphs that contain a vertex whose removal leaves an outerplanar graph is also minor-closed. We provide the complete list of 57 excluded minors for this class.     

The existence of generalized mix functions

To enrich the message space of a cipher and guarantee security, Ristenpart and Rogaway defined mix functions on two sets of equal size. To mix inputs from two sets of different sizes, Stinson generalized the definition of mix functions (called generalized mix functions), and established an existence result for generalized mix functions with 10 undetermined pairs of input sizes. In this paper, we complete the solution to the existence problem for generalized mix functions.      

Decomposable polymatroids and connections with graph coloring

We introduce ideas that complement the many known connections between polymatroids and graph coloring. Given a hypergraph that satisfies certain conditions, we construct polymatroids, given as rank functions, that can be written as sums of rank functions of matroids, and for which the minimum number of matroids required in such sums is the chromatic number of the line graph of the hypergraph. This result motivates introducing chromatic numbers and chromatic polynomials for polymatroids. We show that the chromatic polynomial of any 2-polymatroid is a rational multiple of the chromatic polynomial of some graph. We also find the excluded minors for the minor-closed class of polymatroids that can be written as sums of rank functions of matroids that form a chain of quotients.     

Symmetry in c, d, n of Jacobian elliptic functions

The relation connecting the symmetric elliptic integral RF with the Jacobian elliptic functions is symmetric in the first three of the four letters c, d, n, and s that are used in ordered pairs to name the 12 functions. A symbol Δ(p,q)=ps²(u,k)−qs²(u,k), p,q∈{c,d,n}, is independent of u and allows formulas for differentiation, bisection, duplication, and addition to remain valid when c, d, and n are permuted. The five transformations of first order, which change the argument and modulus of the functions, take a unified form in which they correspond to the five nontrivial permutations of c, d, and n. There are 18 transformations of second order (including Landen's and Gauss's transformations) comprising three sets of six. The sets are related by permutations of the original functions cs, ds, and ns, and there are only three sets because each set is symmetric in two of these. The six second-order transformations in each set are related by first-order transformations of the transformed functions, and all 18 take a unified form. All results are derived from properties of RF without invoking Weierstrass functions or theta functions.     

Calculus of Generalized Quasi－differentiable Functions Ⅰ：Some Results on the Space of Pairs of Convex－Set Collections

A Riesz space K1 whose elements are pairs of convex-set collections is presented for the study on the calculus of generalized quasi-differentiable functions.The space K1 is constructed by introducing a well-defined equivalence reation among pairs of collections of convex sets .Some important properties on the norm and operations is K1 are given.     

Denotational semantics for intuitionistic type theory using a hierarchy of domains with totality

A modified version of Normann's hierarchy of domains with totality [9] is presented and is shown to be suitable for interpretation of Martin-L?f's intuitionistic type theory. This gives an interpretation within classical set theory, which is natural in the sense that -types are interpreted as sets of pairs and -types as sets of choice functions. The hierarchy admits a natural definition of the total objects in the domains, and following an idea of Berger [3] this makes possible an interpretation where a type is defined to be true if its interpretation contains a total object. In particular, the empty type contains no total objects and will therefore be false (in any non-empty context). In addition, there is a natural equivalence relation on the total objects, so we derive a hierarchy of topological spaces (quotient spaces wrt. the Scott topology), and give a second interpretation using this hierarchy. Received: 11 December 1995 / Revised version: 14 October 1996     

A topological approach to divisibility of arithmetical functions and GCD matrices

Considering lower closed sets as closed sets on a preposet (P, ≤), we obtain an Alexandroff topology on P. Then order preserving functions are continuous functions. In this article we investigate order preserving properties (and thus continuity properties) of integer-valued arithmetical functions under the usual divisibility relation of integers and power GCD matrices under the divisibility relation of integer matrices.     

Rough approximation of a preference relation by dominance relations

An original methodology for using rough sets to preference modeling in multi-criteria decision problems is presented. This methodology operates on a pairwise comparison table (PCT), including pairs of actions described by graded preference relations on particular criteria and by a comprehensive preference relation. It builds up a rough approximation of a preference relation by graded dominance relations. Decision rules derived from the rough approximation of a preference relation can be used to obtain a recommendation in multi-criteria choice and ranking problems. The methodology is illustrated by an example of multi-criteria programming of water supply systems.     

On Nondeterminism,Enumeration Reducibility and Polynomial Bounds

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e-reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non-deterministic polynomial time reducibility. We define the polynomial time e-degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.     

Subdivision Schemes of Sets and the Approximation of Set-Valued Functions in the Symmetric Difference Metric

In this work we construct subdivision schemes refining general subsets of ? ⁿ and study their applications to the approximation of set-valued functions. Differently from previous works on set-valued approximation, our methods are developed and analyzed in the metric space of Lebesgue measurable sets endowed with the symmetric difference metric. The construction of the set-valued subdivision schemes is based on a new weighted average of two sets, which is defined for positive weights (corresponding to interpolation) and also when one weight is negative (corresponding to extrapolation). Using the new average with positive weights, we adapt to sets spline subdivision schemes computed by the Lane–Riesenfeld algorithm, which requires only averages of pairs of numbers. The averages of numbers are then replaced by the new averages of pairs of sets. Among other features of the resulting set-valued subdivision schemes, we prove their monotonicity preservation property. Using the new weighted average of sets with both positive and negative weights, we adapt to sets the 4-point interpolatory subdivision scheme. Finally, we discuss the extension of the results obtained in metric spaces of sets, to general metric spaces endowed with an averaging operation satisfying certain properties.     

An approach to spectral sets of certain zeta-functions

A. Beurling introduced the concept of spectral sets of unbounded functions to study the possibility of the approximation of those by trigonometric polynomials. The author studied spectral sets of the Riemann zeta-function and zeta-functions belonging to a certain class. The purpose of the present paper is to improve the results in the previous studies for spectral sets. The improvement is based on the relation between spectral sets and support of distributions.