Axiomatizability of reducts of algebras of relations

In this paper, we prove that any subreduct of the class of representable relation algebras whose similarity type includes intersection, relation composition and converse is a non-finitely axiomatizable quasivariety and that its equational theory is not finitely based. We show the same result for subreducts of the class of representable cylindric algebras of dimension at least three whose similarity types include intersection and cylindrifications. A similar result is proved for subreducts of the class of representable sequential algebras. Received October 7, 1998; accepted in final form September 10, 1999.     

Generalized Serre relations for Lie algebras associated with positive unit forms

Every semisimple Lie algebra defines a root system on the dual space of a Cartan subalgebra and a Cartan matrix, which expresses the dual of the Killing form on a root base. Serre’s Theorem [J.-P. Serre, Complex Semisimple Lie Algebras (G.A. Jones, Trans.), Springer-Verlag, New York, 1987] gives then a representation of the given Lie algebra in generators and relations in terms of the Cartan matrix.In this work, we generalize Serre’s Theorem to give an explicit representation in generators and relations for any simply laced semisimple Lie algebra in terms of a positive quasi-Cartan matrix. Such a quasi-Cartan matrix expresses the dual of the Killing form for a Z-base of roots. Here, by a Z-base of roots, we mean a set of linearly independent roots which generate all roots as linear combinations with integral coefficients.     

Ranks of binary relations

This paper clarifies the notion of rank of a binary relation. Indeed several definitions cohabit in the literature and two of them have never been distinguished. The main results concern the comparison of these two notions. We show that the two definitions are really different, even under strong restrictive conditions about the algebraic structure of the semigroup.     

Groups of binary relations

It was shown in [3] that every finite group is the maximal subgroup of a semigroupB _x of all binary relations on some finite set X. This result is extended here to arbitrary groups.     

Properties of algebras of binary functions

Translated from Matematicheskie Zametki, Vol. 55, No. 1, pp. 130–140, January, 1994.     

Isomorphisms of algebras of binary functions

Translated from Matematicheskie Zametki, Vol. 55, No. 4, pp. 120–127, April, 1994.     

The structure of solid binary algebras

A solid binary algebra in an abstract characterisation of the idempotents of a completely regular semigroup. We present here a structure theorem for solid binary algebras in terms of semilattices and rectangular bands. We also show that a free solid binary algebra can be embedded in a free completely regular semigroup; thus the word problem for the free solid binary algebra can be solved by using a solution of the word problem for the free completely regular semigroup.Presented by B. M. Schein.The author gratefully acknowledges the financial support of an Australian Postgraduate Research Award.     

Hypergroups and binary relations

The paper deals with a binary relation R on a set H, where the Rosenberg partial hypergroupoid H _R is a hypergroup. It proves that if H _R is a hypergroup, S is an extension of R contained in the transitive closure of R and S ², then H _S is also a hypergroup. Corollaries for various extensions of R, the union, intersection and product constructions being employed, are then proved. If H _R and H _S are mutually associative hypergroups then is proven to be a hypergroup. Lastly, a tree and an iterative sequence of hyperoperations where k = 1, 2, ...) on its vertices are considered. A bound on the diameter of is given for each k such that is associative. Received December 18, 1998; accepted in final form February 8, 2000.     

Operations on binary relations

The effects of five basic operations (asymmetrization, complementation, dualization, symmetrization, transitive closure) on binary relations are examined. Identifies between compound operations are developed (e.g. the symmetric part of the transitive closure of the complement of the transitive closure equals the transitive closure of the symmetric complement of the transitive closure), ordering aspects of compound operations are noted, and it is shown that in addition to the empty and universal relations at most 110 different relations can be generated from a given binary relation by sequential applications of the five basic operations. Moreover, 110 is the least upper bound, and none of these 110 requires more than seven applications of the basic operations for its expression. One of the potentially irreducible compound operations of length seven is cstcatc, the complement of the symmetric part of the transitive closure of the complement of the asymmetric part of the transitive closure of the complement.     

Traces of fuzzy binary relations

In this paper the right and left trace of a fuzzy binary relation is defined and investigated. Basic properties of a fuzzy relation (such as reflexivity, different kinds of transitivity, linearity, etc.) are characterized by means of its traces.     

Sandwich semigroups of binary relations

This paper introduces new semigroups of binary relations that arose naturally from investigating the transfer of information between automata and semigroups associated with automata. In particular we introduce a new multiplication on binary relations by means of an arbitrary but fixed “sandwich” relation. R.J. Plemmons and M. West have characterized Green's relations in the usual semigroup of binary relations, and we use these to investigate Green's relations in our semigroups. We give algorithms for constructing idempotents and regular elements in these new semigroups.     

Representation of binary systems by families of binary relations

It is proved that an arbitrary binary multiplicative system can be represented by a family of binary relations, using the so called generalized multiplication of relations. Transformations of such representations and existence of a ‘universal’ representation are studied.     

Enumeration of algebras close to absolutely free algebras and binary trees

We study three classes of algebras: absolutely free algebras, free commutative non-associative, and free anti-commutative non-associative algebras. We study asymptotics of the growth for free algebras of these classes and for their subvarieties as well. Mainly, we study finitely generated algebras, also the codimension growth for varieties in theses classes is studied. For these purposes we use ordinary generating functions as well as exponential generating functions. The following subvarieties are studied in these classes: solvable, completely solvable, right-nilpotent, and completely right-nilpotent subvarieties. The obtained results are equivalent to an enumeration of binary labeled and unlabeled rooted trees that do not contain some forbidden subtrees. We enumerate these trees using generating functions. For solvable and right-nilpotent algebras the generating functions are algebraic. For completely solvable and completely right-nilpotent algebras the respective functions are rational. It is known that these three varieties of algebras satisfy Schreier's property, i.e., subalgebras of free algebras are free. For free groups, there is Schreier's formula for the rank of a subgroup of a free group. We find analogues of this formula for these varieties. They are written in terms of series. As an application, we study invariants of finite groups acting on absolutely free algebras.     

Quasivarieties of Graphs and Independent Axiomatizability

In the present article, we continue to study the complexity of the lattice of quasivarieties of graphs. For every quasivariety K of graphs that contains a non-bipartite graph, we find a subquasivariety K′ ? K such that there exist 2^ω subquasivarieties K″ ∈ L_q(K′) without covers (hence, without independent bases for their quasi-identities in K′).