On deciding whether a monoid is a free monoid or is a group

Summary In general it is undecidable whether or not the monoid described by a given finite presentation is a free monoid or a group. However, these two decision problems are reducible to a very restricted form of the uniform word problem. So whenever a class of presentations is considered for which this restricted form of the uniform word problem is decidable, then the above decision problems become decidable. This holds in particular for the class of all presentations involving finite string-rewriting systems that are noetherian and confluent.     

Generic Complexity of Finitely Presented Monoids and Semigroups

We study the generic properties of finitely presented monoids and semigroups, and the generic-case complexity of decision problems for them. We show that for a finite alphabet A of size at least 2 and positive integers k and m, the generic A-generated k-relation monoid and semigroup (defined using any of several stratifications) satisfies the small overlap condition C(m). It follows that the generic finitely presented monoid has a number of interesting semigroup-theoretic properties and, by a recent result of the author, admits a linear time solution to its word problem and a regular language of unique normal forms for its elements. Moreover, the uniform word problem for finitely presented monoids is generically solvable in polynomial time.     

Undecidable properties of monoids with word problem solvable in linear time

Let C₁ be the class of finitely presented monoids with word problem solvable in linear time. Let P be a Markov property of monoids related to class C₁ in some sense. It is undecidable given a monoid in C₁ whether it satisfies P. Let C and C′ be classes of finitely presented monoids with word problem solvable in some time-bounds. If C contains C₁ and C′ properly contains C, then it is undecidable given a monoid in C′ whether it belongs to C.     

Inverse monoids: Decidability and complexity of algebraic questions

This paper investigates the word problem for inverse monoids generated by a set Γ subject to relations of the form e = f, where e and f are both idempotents in the free inverse monoid generated by Γ. It is shown that for every fixed monoid of this form the word problem can be solved both in linear time on a RAM as well as in deterministic logarithmic space, which solves an open problem of Margolis and Meakin. For the uniform word problem, where the presentation is part of the input, EXPTIME-completeness is shown. For the Cayley-graphs of these monoids, it is shown that the first-order theory with regular path predicates is decidable. Regular path predicates allow to state that there is a path from a node x to a node y that is labeled with a word from some regular language. As a corollary, the decidability of the generalized word problem is deduced.     

Syntactic complexity of context-free grammars over word monoids

 The syntactic complexity of context-free grammars defined over word monoids is investigated. It is demonstrated that every recursively enumerable language can be defined by a ten-nonterminal context-free grammar over a word monoid generated by an alphabet and six words of length two. Open problems are formulated. Received October 10, 1994/February 23, 1995     

On properties not inherited by monoids from their Schützenberger groups

We give an example of a monoid with finitely many left and right ideals, all of whose Schützenberger groups are presentable by finite complete rewriting systems, and so each have finite derivation type, but such that the monoid itself does not have finite derivation type, and therefore does not admit a presentation by a finite complete rewriting system. The example also serves as a counterexample to several other natural questions regarding complete rewriting systems and finite derivation type. Specifically it allows us to construct two finitely generated monoids M and N with isometric Cayley graphs, where N has finite derivation type (respectively, admits a presentation by a finite complete rewriting system) but M does not. This contrasts with the case of finitely generated groups for which finite derivation type is known to be a quasi-isometry invariant. The same example is also used to show that neither of these two properties is preserved under finite Green index extensions.     

Finite Derivation Type Implies The Homological Finiteness Condition FP3

A monoid M that admits a finite convergent presentation satisfies the homological finiteness condition FP∞ and Squier's combinatorial property of having finite derivation type. Although Squier has given an example of a finitely presented monoid S₁ that satisfies the condition FP∞, but that does not have finite derivation type, the exact relationship between these two conditions is unsolved. Here we establish a partial result by showing that for finitely presented monoids the property of having finite derivation type implies the homological finiteness conditions FP₃ . Hence, the property FP₃ is strictly weaker than the property of having finite derivation type.     

Monoïdes syntactiques des langages algébriques

Summary Syntactic monoids have been considered so far almost only for rational (= regular) languages. We start here a systematic study of the syntactic monoids of algebraic (= context-free) languages. We exhibit a whole class of finitely generated monoids, none of which is isomorphic to the syntactic monoid of an algebraic language. We show that if M ₁ and M ₂ are syntactic monoids of algebraic languages L ₁ and L ₂, and if neither M ₁ nor M ₂ has a zero, then there exists an algebraic language L whose syntactic monoid is isomorphic to the direct product M ₂×M₂. We then prove that the algebraic language ¯L ₀ Complement of {n ⁿ yⁿ zⁿ; n1} has a syntactic monoid M ₀ such that M ₀×M ₀ is not isomorphic to the syntactic monoid of any algebraic language, whence follows that any algebraic language L whose syntatic monoid is isomorphic to M ₀ must be non deterministic.     

Decidability Equivalence between the Star Problem and the Finite Power Problem in Trace Monoids

In the last decade, research on the star problem in trace monoids (is the iteration of a recognizable language also recognizable?) has pointed out the importance of the finite power property to achieve partial solutions to this problem. We prove that the star problem is decidable in some trace monoid if and only if, in the same monoid, it is decidable whether a recognizable language has the finite power property. Intermediate results allow us to give a shorter proof for the decidability of the two previous problems in every trace monoid without a C4 submonoid. We also deal with some earlier ideas, conjectures, and questions which have been raised in the research on the star problem and the finite power property, e.g., we show the decidability of these problems for recognizable languages which contain at most one non-connected trace. Received April 29, 1999, and in revised form November 8, 2000 and in final form November 24, 2000. Online publication February 26, 2001.     

Pseudo-natural algorithms for finitely generated presentations of monoids and groups

Let G be a finitely generated group such that the word problem for G is E_n-decidable for some n≥1. Then there exists a finitely generated context-sensitive presentation of G such that the word problem for this presentation can be solved by a pseudo-natural algorithm in the class E_n. This result cannot be strengthened to always yield a context-free presentation. However, it can be extended to hold for finitely generated monoids as well.     

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.     

Some Properties of Iterated Languages

A special kind of substitution on languages called iteration is presented and studied. These languages arise in the application of semantic automata to iterations of generalized quantifiers. We show that each of the star-free, regular, and deterministic context-free languages are closed under iteration and that it is decidable whether a given regular or determinstic context-free language is an iteration of two such languages. This result can be read as saying that the van Benthem/Keenan ‘Frege Boundary’ is decidable for large subclasses of natural language quantifiers. We also determine the state complexity of iteration of regular languages.     

A Completion Procedure for Finitely Presented Groups That Is Based on Word Cycles

A Knuth–Bendix-style completion procedure for groups is presented that, instead of working with sets of string-rewriting rules, manipulates finite sets of word cycles. A characterization is given for the resulting sets of persistent word cycles, from which it follows that the completion procedure terminates successfully if and only if the reduced word problem of the finite group presentation considered is a finite set. In this case the resulting set of persistent word cycles yields a finite canonical string-rewriting system for every linear reduction ordering.     

Finite complete rewriting systems and the complexity of the word problem

Summary It is well known that the word problem for a finite complete rewriting system is decidable. Here it is shown that in general this result cannot be improved. This is done by proving that each sufficiently rich complexity class can be realized by the word problem for a finite complete rewriting system. Further, there is a gap between the complexity of the word problem for a finite complete rewriting system and the complexity of the least upper bound for the lengths of the chains generated by this rewriting system, and this gap can get arbitrarily large. Thus, the lengths of these chains do not give any information about the complexity of the word problem. Finally, it is shown that the property of allowing a finite complete rewriting system is not an invariant of finite monoid presentations.Some of the results presented here are from the doctoral dissertation of the first author, which was supervised by Prof. H. Brakhage at the University of Kaiserslautern     

Two collapsing hierarchies of subregularly tree controlled languages

Tree controlled grammars are context-free grammars where the associated language only contains those terminal words which have a derivation where the word of any level of the corresponding derivation tree belongs to a given regular language. In this paper, we consider first as control sets such regular languages which can be represented by finite unions of monoids. We show that the corresponding hierarchy of tree controlled languages collapses already at the second level. Second, we restrict the number of states allowed in the accepting automaton of the regular control language. We prove that the associated hierarchy has at most five levels.     

On the automaticity of singular Artin monoids of finite type

Automaticity is an important concept in group theory as it yields an efficient solution to the word problem and provides other possibilities for effective computation. The concept of automaticity generalizes naturally from groups to monoids and semigroups and the efficiency of the solution of the word problem is preserved when we do this. Whilst this subject has been studied extensively (in both the group and the monoid/semigroup case), there are still some deep and major open problems, including questions concerning the automaticity of certain naturally occurring classes of groups, monoids and semigroups. In this paper, we consider two such classes of monoids, namely the positive singular Artin monoids of finite type and the singular Artin monoids of the finite type. The main purpose here is to show that these monoids are all automatic. When establishing the automaticity of monoids, one obstacle is that we often have asynchronous finite automata recognizing multiplication and we need to establish the existence of synchronous machines accomplishing the same task. Building on the work of Frougny and Sakarovitch, we establish a new criterion for achieving such a transition; this is fundamental in the establishment of the automaticity of the monoids we consider here and may well apply to other naturally occurring classes of monoids and semigroups as well.     

Palindrome words and reverse closed languages

A word which is equal to its mirror image is called a palindrome word. Any language consisting of palindrome words is called a palindrome language. In this paper we investigate properties of palindrome words and languages. We show that there is no dense regular language consisting of palindrome words. A language contains all the mirror images of its elements is called a reverse closed language. Clearly, every palindrome language is reverse closed. We show that whether a given regular or context-free language is reverse closed is decidable. We study certain properties concerning reverse closed finite maximal prefix codes in this paper. Properties of languages that commute with reverse closed languages are investigated too.     

New Results on the Star Problem in Trace Monoids

We prove that if it is decidable whether X* is recognizable for a recognizable subset X of a free partially commutative monoid, then it is decidable whether a recognizable subset of a free partially commutative monoid possesses the finite power property. We prove that if any trace of a set X is connected, we can decide whether X possesses the finite power property. Finally, we also show that if X is a finite set containing at most four traces or at most two connected traces, it is decidable whether X* is recognizable.