When is a monoid a group? the Church-Rosser case is tractable

The following question is shown to be tractable: given a finite monadic Church-Rosser Thue system T and a finite set A, is the submonoid generated by A (of the monoid presented by T) a group?     

The poset of retracts of a free monoid

The set of retracts of a free monoid F with the partial order of inclusion is investigated. This poset is a lattice if and only if F is generated by three or fewer elements. For a finitely generated free monoid F it is shown non-constructively that, for every submonoid S of F, the intersection of all retracts of F containing S is regular. A regular expression can be constructed for this intersection when S is regular. The submonoid generated by the set of all retracts of F contained in the regular submonoid S is also regular and constructable. This allows the decision to be made whether or not any given pair of retracts has a supremum or an infimum in the poset of retracts of F. The procedure yields regular expressions for such suprema and infima when they exist.     

Onω-Languages whose syntactic monoid is trivial

For a languageL the syntactic monoid SynL is trivial if and only if indeedL itself is trivial, that isL = Ø orL=X*. As a surprise one realizes that the syntactic monoid SynL of an ω-languageL being trivial by no means implies thatL be trivial. This situation is analyzed in this paper. The results may help clarify the difference between deterministically and nondeterministically finite state acceptable ω-languages.     

The lattice of semiretracts of a free monoid

The poset of retracts of a free monoid F is a lattice only when F is generated by three or fewer elements. We extend this result by widening attention from the retracts of F to the finite intersections of retracts, which we call semiretracts. When F is generated by three or fewer elements every semiretract is a retract. We obtain the desired generalization: The semiretracts of a finitely generated free monoid form a complete lattice. Moreover, each such lattice satisfies the ascending and descending chain conditions. These results are demonstrated through the use of special features of the minimal generating sets of retracts of free monoids.     

States and the free orthogonality monoid

Let (X, #) be an orthogonality space such that the lattice C(X, #) of closed subsets of (X, #) is orthomodular and let (, ) denote the free orthogonality monoid over (X, #). Let C₀(, ) be the subset of C(, ), consisting of all closures of bounded orthogonal sets. We show that C₀(, ) is a suborthomodular lattice of C(, ) and we provide a necessary and sufficient condition for C₀(, ) to carry a full set of dispersion free states.The work of the second author on this paper was supported by National Science Foundation Grant GP-9005.     

On a special monoid with a single defining relation

We show that no finite union of congruence classes [w], w being an arbitrary element of the free monoid {a, b}¹ with unit 1, is a context-free language if the congruence is defined by the single pair (abbaab, 1). This congruence is neither confluent nor even preperfect. The monoid formed by its congruence classes is a group which has infinitely many isomorphic proper subgroups.     

On Nonnegative matrices generating a finite multiplicative monoid

Square nonnegative matrices with the property that the multiplicative monoid M(A) generated by the matrix A is finite are characterized in several ways. At first, the least general upper bound for the cardinality of M(A) is derived. Then it is shown that any square nonnegative matrix is cogredient to a lower triangular block form with the diagonal consisting of three blocks L, A ₀, and M where L and M are strictly lower triangular, A ₀ has no zero rows or columns, and M(A) is finite if and only if. M(A ₀) is so. Several criteria for, M(A ₀) to be finite are presented. One of the normal forms of A applies very well to the characterization of the nonnegative solutions of each of the matrix equations X ^k = 0, X ^k = 1, X ^k = X, and X ^k = X ^T where k > 1 is an integer. It also leads to a polynomial time algorithm for deciding whether or not M(A) is finite, if the entries of A are nonnegative rationals.     

On deciding subsumption problems

Subsumption is an important redundancy elimination method in automated deduction. A clause D is subsumed by a set of clauses if there is a clause C and a substitution such that the literals of C are included in D. In the field of automated model building, subsumption has been modified to an even stronger redundancy elimination method, namely the so-called clausal H-subsumption. Atomic H-subsumption emerges from clausal H-subsumption by restricting D to an atom and to a set of atoms. Both clausal and atomic H-subsumption play an indispensable key role in automated model building. Moreover, problems equivalent to atomic H-subsumption have been studied with different terminologies in many areas of computer science. Both clausal and atomic H-subsumption are known to be intractable, i.e., _p ² -complete and NP-complete, respectively. In this paper, we present a new approach to deciding (clausal and atomic) H-subsumption that is based on a reduction to QSAT₂ and SAT, respectively.This was partially supported by the Austrian Science Foundation under grant P15068. We thank the anonymous referees for valuable comments.     

On deciding subsumption problems

Subsumption is an important redundancy elimination method in automated deduction. A clause D is subsumed by a set C of clauses if there is a clause CC and a substitution such that the literals of C are included in D. In the field of automated model building, subsumption has been modified to an even stronger redundancy elimination method, namely the so-called clausal H-subsumption. Atomic H-subsumption emerges from clausal H-subsumption by restricting D to an atom and C to a set of atoms. Both clausal and atomic H-subsumption play an indispensable key role in automated model building. Moreover, problems equivalent to atomic H-subsumption have been studied with different terminologies in many areas of computer science. Both clausal and atomic H-subsumption are known to be intractable, i.e., ₂ ^p -complete and NP-complete, respectively. In this paper, we present a new approach to deciding (clausal and atomic) H-subsumption that is based on a reduction to QSAT₂ and SAT, respectively.     

On the rational subsets of the free group

 We show that every rational subset of a free group of finite rank is either disjunctive or has finite index. We then generalise this result to virtually free groups: if G is virtually free and R is a rational subset of G, then the syntactic normal subgroup N of R is either finite or has finite index. Received November 25, 1992/February 3, 1995     

On deciding finiteness of matrix groups

We provide a new, practical algorithm for deciding finiteness of matrix groups over function fields of zero characteristic. The algorithm has been implemented in GAP. Experimental results and extensions of the algorithm to any field of zero characteristic are discussed.     

It is decidable whether a monadic thue system is canonical over a regular set

A restricted confluence problem is investigated for string-rewriting systems (Thue systems). It is shown that it is decidable whether a monadic Thue system is canonical over a regular set; i.e., there is an algorithm to determine whether every string in a regular set has a unique normal form modulo a monadic Thue system.This work was supported by the Natural Sciences and Engineering Research Council of Canada. It was done while the author was visiting the Department of Computer Science, University of Calgary, Alberta, Canada T2N 1N4.     

Finite complete rewriting systems for the Jantzen monoid and the greendlinger group

It is shown that for the presentation (a, b; abbaab = λ) of the Jantzen monoid J no finite complete rewriting system exist that is based on a Knuth-Bendix ordering. However, a finite complete rewriting system is given for a different presentation of J that has four generators. Further, a finite complete rewriting system is given for the presentation 〈a, b, c; abc = cba〉 of the Greendlinger group G. This system induces a polynomial-time algorithm for the word problem for G.     

On deciding the confluence of a finite string-rewriting system on a given congruence class

In general it is undecidable whether or not a given finite string-rewriting system R is confluent on a given congruence class [w]_R, even when only length-reducing systems are considered. However, for finite monadic string-rewriting systems this problem becomes decidable in double exponential time. For certain subclasses of monadic string-rewriting systems algorithms of lower complexity are obtained for solving this problem.     

On algorithmically checking whether a Hilbert series comes from a complete intersection

It is not possible to determine from the Hilbert series whether a commutative -graded Noetherian algebra is a complete intersection. Nevertheless, the Hilbert series of a complete intersection satisfies very stringent conditions and we define a concept CI-type for formal power series, that embodies some of these necessary properties. This definition becomes interesting mainly for algebras that are not standard i.e. not generated in degree 1. For the class of formal power series that occur as the Hilbert series of -graded Noetherian Cohen–Macaulay algebras, the main result is a criterion for a series to be of CI-type, that is formulated in terms of properties of truncated power series. Hence it can be used as the basis for an algorithm that provides in a finite number of steps either a rational function expression of the formal power series, or the information that the truncated power series is not of CI-type. Also sample computations using this algorithm on some non-standard graded invariant algebras are described.     

On the complexity of deciding typability in the relational algebra

We investigate the complexity of the typability problem for the relational algebra. This problem consists of deciding, for a given relational algebra expression, whether there exists an assignment of types to variables occurring in the expression such that the expression is well-typed under the assignment. We obtain that the problem is NP-complete in general. In particular, we show that the problem becomes NP-hard due to (1) the cartesian product operator, (2) the selection operator on arbitrary sets of typed predicates, (3) the selection operator on well-behaved sets of typed predicates together with join and projection or renaming. However, the problem is in P when (1) we only allow union, difference, join and selection on well-behaved sets of typed predicates, or (2) we allow all operators except cartesian product, where the set of selection predicates can mention at most one base type. Most of these results follow from a close connection of the typability problem to non-uniform constraint satisfaction.Received: 18 February 2004, Published online: 14 March 2005Stijn Vansummeren: Research Assistant of the Fund for Scientific Research - Flanders (Belgium)     

On determining whether two polynomials are relatively prime

A comparison is made of the computational effort required for four different algorithms which establish whether two monic polynomials have a common zero. Two of the algorithms are based on the vanishing of the resultant and the other two on a recent theorem of Vogt and Bose.