International Journal of Algebra and Computation

In this paper, we discuss the different notions of local topological density for subsets of the free monoid A*. We introduce the notion of weak completeness for a set X, relatively to an arbitrary submonoid M of A*.

For the so-called strongly M-thin codes, we establish that weak completeness is equivalent to maximality in M. This constitutes a new generalization of a famous result due to Schützenberger.

We consider the algebra U_n(K) of n×n upper triangular matrices over an infinite field K equipped with its usual ℤ_n-grading. We describe a basis of the ideal of the graded polynomial identities for this algebra.

We link the Dehn function of finitely presented groups to the length-of-proofs function in propositional proof complexity.

For a positive integer n, we denote by SUB (respectively, SUB_n) the class of all lattices that can be embedded into the lattice Co(P) of all order-convex subsets of a partially ordered set P (respectively, P of length at most n). We prove the following results:

(1) SUB_n is a finitely based variety, for any n≥1.

(2) SUB₂ is locally finite.

(3) A finite atomistic lattice L without D-cycles belongs to SUB if and only if it belongs to SUB₂; this result does not extend to the nonatomistic case.

(4) SUB_n is not locally finite for n≥3.

We consider two different types of bounded height condition for semigroups. The first one originates from the classical Shirshov's bounded height theorem for associative rings. The second which is weaker, in fact was introduced by Wolf and also used by Bass for calculating the growth of finitely generated (f.g.) nilpotent groups. Both conditions yield polynomial growth. We give the first two examples of f.g. semigroups which have bounded height and do not satisfy any nontrivial identity. One of these semigroups does not have bounded height in the sense of Shirshov and the other satisfies the classical bounded height condition. This develops further one of the main results of the author's paper (J. Algebra, 1993) where the first examples of f.g. semigroups of polynomial growth and without nontrivial identities were given.

We prove that for λ≥1 and all sufficiently large ∊, the set of (λ,∊)-quasigeodesics in an infinite word-hyperbolic group G is regular if and only if λ is rational. In fact, this set of quasigeodesics defines an asynchronous automatic structure for G. We also introduce the idea of an exact (λ,∊)-quasigeodesic and show that for rational λ and appropriate ∊ the sets of exact (λ,∊)-quasigeodesics define synchronous automatic structures.

A semiring with involution is a semiring equipped with an involutorial antiasutomorphism as a fundamental operation. The aim of the present paper is to determine the lattice of all varieties of idempotent and distributive semirings with involution. We start with the description of their structure, which is followed by a complete list of all subdirectly irreducibles. We make a heavy use of general results obtained recently by Dolinka and Vinčić [11] on involutorial Płonka sums. Applying these results and some further structural theorems, we construct the considered lattice. It turns out that it has exactly 64 elements.