On the finite basis problem for the monoids of partial extensive injective transformations

Let \(PEI_n (POEI_n)\) be the monoid of all partial (order-preserving) extensive and injective transformations over a chain of order n. We give a sufficient condition under which a semigroup is nonfinitely based and apply this condition to show that the monoid \(PEI_3 (POEI_3)\) is nonfinitely based. This together with the results of Edmunds and Goldberg gives a complete answer to the finite basis problem for the monoid \(PEI_n (POEI_n)\): the monoid \(PEI_n (POEI_n)\) is nonfinitely based if and only if \(n\geqslant 3\). Furthermore, it is shown that the monoid \(PEI_n (POEI_n)\) is hereditarily finitely based if and only if \(n\leqslant 2\).     

Finite basis problem for 2-testable monoids

A monoid S ¹ obtained by adjoining a unit element to a 2-testable semigroup S is said to be 2-testable. It is shown that a 2-testable monoid S ¹ is either inherently non-finitely based or hereditarily finitely based, depending on whether or not the variety generated by the semigroup S contains the Brandt semigroup of order five. Consequently, it is decidable in quadratic time if a finite 2-testable monoid is finitely based.     

On the hall exponents of boolean matrices

We obtain upper bounds on the Hall exponents of symmetric and microsymmetric primitive Boolean matrices respectively.     

On the generalized indices of boolean matrices

We characterize completely those Boolean matrices with the largest generalized indices in the class of Boolean matrices and in the class of reducible Boolean matrices and derive a new upper bound for the generalized index in terms of period. We also generalize the upper and lower multiexponents of primitive Boolean matrices to general Boolean matrices.     

On the generalized indices of boolean matrices

We characterize completely those Boolean matrices with the largest generalized indices in the class of Boolean matrices and in the class of reducible Boolean matrices and derive a new upper bound for the generalized index in terms of period. We also generalize the upper and lower multiexponents of primitive Boolean matrices to general Boolean matrices.     

On the hall exponents of boolean matrices

We obtain upper bounds on the Hall exponents of symmetric and microsymmetric primitive Boolean matrices respectively.     

On the divisibility problem for one-relator monoids

This work was supported by the Russian Foundation for Fundamental Research (Under Grant No. 93-011-16015).     

On the finite basis problem for certain 2-limited words

Let X* be a free monoid over an alphabet X and W be a finite language over X. Let S(W) be the Rees quotient X*/I(W), where I(W) is the ideal of X* consisting of all elements of X* that are not subwords of W. Then S(W) is a finite monoid with zero and is called the discrete syntactic monoid of W. W is called finitely based if the monoid S(W) is finitely based. In this paper, we give some sufficient conditions for a monoid to be non-finitely based. Using these conditions and other results, we describe all finitely based 2-limited words over a three-element alphabet. Furthermore, an explicit algorithm is given to decide that whether or not a 2-limited word in which there are exactly two non-linear letters is finitely based.     

On a finite basis problem for universal positive formulas

A finite semigroup without a finite basis of collective identities has been constructed. A semigroup with a finite basis of identities, but without a finite basis of disjunctive identities has been constructed.Presented by B. M. Schein.     

On the eigenvalue problem for a particular class of finite Jacobi matrices

A function f with simple and nice algebraic properties is defined on a subset of the space of complex sequences. Some special functions are expressible in terms of f, first of all the Bessel functions of first kind. A compact formula in terms of the function f is given for the determinant of a Jacobi matrix. Further we focus on the particular class of Jacobi matrices of odd dimension whose parallels to the diagonal are constant and whose diagonal depends linearly on the index. A formula is derived for the characteristic function. Yet another formula is presented in which the characteristic function is expressed in terms of the function f in a simple and compact manner. A special basis is constructed in which the Jacobi matrix becomes a sum of a diagonal matrix and a rank-one matrix operator. A vector-valued function on the complex plain is constructed having the property that its values on spectral points of the Jacobi matrix are equal to corresponding eigenvectors.     

On the complexity of linear boolean operators with thin matrices

Under consideration is the problem of constructing a square Booleanmatrix A of order n without “rectangles” (it is a matrix whose every submatrix of the elements that are in any two rows and two columns does not consist of 1s). A linear transformation modulo two defined by A has complexity o(ν(A) − n) in the base {⊕}, where ν(A) is the weight of A, i.e., the number of 1s (the matrices without rectangles are called thin). Two constructions for solving this problem are given. In the first construction, n = p ² where p is an odd prime. The corresponding matrix H _p has weight p ³ and generates the linear transformation of complexity O(p ² log p log log p). In the second construction, the matrix has weight nk where k is the cardinality of a Sidon set in ℤ _n . We may assume that

On fully indecomposable exponent for primitive boolean matrices with symmetric ones

If A is a primitive matrix, then there is a smallest power of A (its fully indecomposable exponent) which is fully indecomposable, and a smallest power of A (its strict fully indecomposable exponent) starting from which all powers are fully indecomposable. We obtain bounds on these two exponents for primitive Boolean matrices with symmetric one's.     

On fully indecomposable exponent for primitive boolean matrices with symmetric ones

If A is a primitive matrix, then there is a smallest power of A (its fully indecomposable exponent) which is fully indecomposable, and a smallest power of A (its strict fully indecomposable exponent) starting from which all powers are fully indecomposable. We obtain bounds on these two exponents for primitive Boolean matrices with symmetric one's.     

On factorization of triangular matrices of the second

The problem of factorization of the matrices of form (5) is investigated. The problem is solved by method from [GGK]. A new criterion for canonical factorization is represented. The explicit form for factors and two examples are given.