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.     

P4-Reducible Graphs—Class of Uniquely Tree-Representable Graphs

We introduce and characterize a new class of graphs which has a unique tree representation, and which strictly contains the well-known class of cographs. We define three graph operations and show that all the graphs in our class can be constructed from single-vertex graphs by a finite sequence of these operations. Finally, we show that a number of computational problems, including the four classical optimization problems, can be solved efficiently for this new class of graphs.     

Congruence permutable MS-algebras

We characterize the congruence permutable MS-algebras in a result analogous to that of Nachbin for distributive lattices. In our main result we prove, among other things, that the congruence permutability of an MS-algebra L is equivalent to the existence of two binary operations in L which satisfy certain equational properties. We show that the class of all congruence permutable MS-algebras with these additional operations forms an equational class. Finally we give a Mal’cev term for this new variety. Presented by J. Berman. Received May 12, 2005; accepted in final form November 5, 2005. Research supported by ANPCyT (Contrato Préstamo BID 1201/OC-AR) and SECyT (UNC)     

Override and update

Override and update are natural constructions for combining partial functions, which arise in various program specification contexts. We use an unexpected connection with combinatorial geometry to provide a complete finite system of equational axioms for the first order theory of the override and update constructions on partial functions, resolving the main unsolved problem in the area.     

Problem with nonlocal two-point condition in time for a homogeneous partial differential equation of infinite order with respect to space variables

We specify a class of unique solvability of a problem with nonlocal boundary condition for a homogeneous partial differential equation of the first order with respect to time and of infinite order with respect to space variables with constant complex coefficients. In the class of quasipolynomials of special form, we indicate formulas for the construction of a solution of the problem that require a finite number of differentiation operations of analytically given functions. For the case where there exists a nonunique solution of the problem, we present an algorithm of the construction of its partial solution.     

Induced modules over group algebras of metabelian groups of finite rank

ABSTRACT

Investigation of multiplace functions by algebraic methods plays an important role in modern mathematics were we consider various operations on sets of functions, which are naturally defined. The basic operation for functions is superposition (composition), but there are some other naturally defined operations, which are also worth of consideration. For example, the operation of set-theoretic intersection and the operation of projections. In this paper we find an abstract characterization of the set of multiplace functions which are closely related to these three operations.     

<Emphasis Type="Italic">K</Emphasis>-finite matrix elements of irreducible Harish-Chandra modules are hypergeometric functions

We show that each K-finite matrix element of an irreducible infinite-dimensional representation of a semisimple Lie group can be obtained from spherical functions by a finite collection of operations. In particular, each matrix element admits a finite expression via the Heckman-Opdam hypergeometric functions.     

Representations of Menger (2, n)-Semigroups by Multiplace Functions

Investigation of partial multiplace functions by algebraic methods plays an important role in modern mathematics, where we consider various operations on sets of functions, which are naturally defined. The basic operation for n -place functions is an (n + 1)-ary superposition [ ], but there are some other naturally defined operations, which are also worth of consideration. In this article we consider binary Mann's compositions ⊕₁,…,⊕ _n for partial n-place functions, which have many important applications for the study of binary and n-ary operations. We present methods of representations of such algebras by n-place functions and find an abstract characterization of the set of n-place functions closed with respect to the set-theoretic inclusion.

Communicated by V. Artamonov.     

Gentzen-style axiomatizations in equational logic

The notion of a Gentzen-style axiomatization of equational theories is presented. In the standard deductive systems for equational logic axioms take the form of equations and the inference rules can be viewed as quasi-equations. In the deductive systems for quasi-equational logic the axioms, which are quasi-equations, can be viewed as sequents and the inference rules as Gentzen-style rules. It is conjectured that every finite algebra has a finite Gentzen-style axiomatization for its quasi-identities. We verify this conjecture for a class of algebras that includes all finite algebras without proper subalgebras and all finite simple algebras that are embeddable into the free algebra of their variety.Dedicated to the memory of Alan DayPresented by J. Sichler.Supported by an Iowa State University Research Assistantship.Supported by National Science Foundation Grant #DMS 8005870.     

Finding all solutions of affine generalized Nash equilibrium problems with one-dimensional strategy sets

We consider a class of generalized Nash equilibrium problems with quadratic cost functions and common linear constraints for all players. Further we focus on the case where every player has a single strategy variable within a bounded set. For this problem class we present an algorithm that is able to compute all solutions and that terminates finitely. Our method is based on a representation of the solution set as a finite union of polyhedral sets using sign conditions for the derivatives of the cost and constraint functions. The effectiveness of the algorithm is shown in various examples from literature.     

Distributive residuated frames and generalized bunched implication algebras

We show that all extensions of the (non-associative) Gentzen system for distributive full Lambek calculus by simple structural rules have the cut elimination property. Also, extensions by such rules that do not increase complexity have the finite model property, hence many subvarieties of the variety of distributive residuated lattices have decidable equational theories. For some other extensions, we prove the finite embeddability property, which implies the decidability of the universal theory, and we show that our results also apply to generalized bunched implication algebras. Our analysis is conducted in the general setting of residuated frames.     

Bounded BCK‐algebras and their generated variety

In this paper we prove that the equational class generated by bounded BCK‐algebras is the variety generated by the class of finite simple bounded BCK‐algebras. To obtain these results we prove that every simple algebra in the equational class generated by bounded BCK‐algebras is also a relatively simple bounded BCK‐algebra. Moreover, we show that every simple bounded BCK‐algebra can be embedded into a simple integral commutative bounded residuated lattice. We extend our main results to some richer subreducts of the class of integral commutative bounded residuated lattices and to the involutive case. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Notes on equational theories of relations

We describe explicitly the free algebras in the equational class generated by all algebras of binary relations with operations of union, composition, converse and reflexive transitive closure and neutral elements 0 (empty relation) and 1 (identity relation). We show the corresponding equational theory is decidable by reducing the problem to a question about regular sets. Similar results are given for two related equational theories.Presented by R. W. Quackenbush.Partially supported by a joint grant from the NSF and the Hungarian Academy of Sciences.Partially supported by a grant from the Hungarian National Foundation for Scientific Research and a joint grant from the NSF and the Hungarian Academy of Sciences. ^v-semirings of 1-closed regular sets. On the basis of this characterization, we conjectured that a set of equational axioms for the variety REL^v consists of equational axioms for the variety L^v and the equation (10). Recently, this conjecture has been proved in [6].     

On decidability of the decomposability problem for finite theories

We consider the decomposability problem for elementary theories, i.e. the problem of deciding whether a theory has a nontrivial representation as a union of two (or several) theories in disjoint signatures. For finite universal Horn theories, we prove that the decomposability problem is $ \sum _1^0 $ \sum _1^0 -complete and, thus, undecidable. We also demonstrate that the decomposability problem is decidable for finite theories in signatures consisting only of monadic predicates and constants.     

Equational spectrum of Hilbert varieties

We prove that an equational class of Hilbert algebras cannot be defined by a single equation. In particular Hilbert algebras and implication algebras are not one-based. Also, we use a seminal theorem of Alfred Tarski in equational logic to characterize the set of cardinalities of all finite irredundant bases of the varieties of Hilbert algebras, implication algebras and commutative BCK algebras: all these varieties can be defined by independent bases of n elements, for each n > 1.      

Conditional sampling for max-stable processes with a mixed moving maxima representation

This paper deals with the question of conditional sampling and prediction for the class of stationary max-stable processes which allow for a mixed moving maxima representation. We develop an exact procedure for conditional sampling using the Poisson point process structure of such processes. For explicit calculations we restrict ourselves to the one-dimensional case and use a finite number of shape functions satisfying some regularity conditions. For more general shape functions approximation techniques are presented. Our algorithm is applied to the Smith process and the Brown-Resnick process. Finally, we compare our computational results to other approaches. Here, the algorithm for Gaussian processes with transformed marginals turns out to be surprisingly competitive.     

Some subdirectly irreducible idempotent semigroups

Subdirectly irreducible idempotent semigroups were characterized in [3], and in that paper, their connection with the various equational classes of idempotent semigroups was discussed. All these results are in terms of identities, so that examples of subdirectly irreducibles in the equational classes are explicitly known only for small classes. It is easy to show from general considerations (see the last section of the present paper) that every proper equational subclass of the class of idempotent semigroups is generated (as an equational class) by one or two subdirectly irreducibles. In this paper we give an example of a subdirectly irreducible for each join irreducible equational class of idempotent semigroups, which generates the class. This list, together with known results, gives explicit examples of one or two finite subdirectly irreducibles which generate the various equational classes. Research supported by the National Research Council of Canada.     

Weakly invariant sets of hybrid systems

We consider a mathematical model of a hybrid system in which the continuous dynamics generated at any point in time by one of a given finite family of continuous systems alternates with discrete operations commanding either an instantaneous switching from one system to another, or an instantaneous passage from current coordinates to some other coordinates, or both operations simultaneously. As a special case, we consider a model of a linear switching system. For a hybrid system, we introduce the notion of a weakly invariant set and analyze its structure. We obtain a representation of a weakly invariant set as a union of sets of simpler structure. For the latter sets, we introduce special value functions, for which we obtain expressions by methods of convex analysis. For the same functions, we derive equations of the Hamilton-Jacobi-Bellman type, which permit one to pass from the problem of constructing weakly invariant sets to the control synthesis problem for a hybrid system.     

On a problem of Wenzel on equational compactness of modules

In this note, we introduce a weak form of equational compactness of modules, which we called x ₀-compactness, together with some of its basic properties. We then use it to settle in the negative a problem of G. H. Wenzel. We also prove the adjacent result that, over a wide class of commutative rings, if every module is x ₀-compact then the ring has finite representation type. Received April 3, 1997; accepted in final form October 1, 1997.