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.     

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 the structure of free finite state machines

The finite state machine U_{m, n}(M) freely generated by a set consisting of m states and n inputs subjects to the relations holding in the finite state machine M was considered by Birkhoff and Lipson in [1, 2]. In this paper, necessary and sufficient conditions for U_{m, n}(M) to consist of m disjoint copies of U_{1, n}(M) are established. The relationship between U_{1, n}(M) and the transition monoid of M, and a representation of U_{1, n}(M) as a transition monoid machine are described. The characterization of machines of type U_{1, n}(M) is in this way reduced to the characterization of finite monoids possessing a ‘universal presentation’. Some general results concerning finite semigroups and groups with a universal presentation, and precise characterizations of finite semilattices and Abelian groups admitting a universal presentation are described.     

Complete involutive rewriting systems

Given a monoid string rewriting system M, one way of obtaining a complete rewriting system for M is to use the classical Knuth–Bendix critical pairs completion algorithm. It is well-known that this algorithm is equivalent to computing a noncommutative Gröbner basis for M. This article develops an alternative approach, using noncommutative involutive basis methods to obtain a complete involutive rewriting system for M.     

Finite complete rewriting systems for regular semigroups

It is proved that, given a (von Neumann) regular semigroup with finitely many left and right ideals, if every maximal subgroup is presentable by a finite complete rewriting system, then so is the semigroup. To achieve this, the following two results are proved: the property of being defined by a finite complete rewriting system is preserved when taking an ideal extension by a semigroup defined by a finite complete rewriting system; a completely 0-simple semigroup with finitely many left and right ideals admits a presentation by a finite complete rewriting system provided all of its maximal subgroups do.     

On Bounded Rational Trace Languages

In this paper, for a finitely generated monoid M, we tackle the following three questions:

1. Is it possible to give a characterization of rational subsets of M which have polynomial growth?
2. What is the structure of the counting function of rational sets which have polynomial growth?
3. Is it true that every rational subset of M has either exponential growth or it has polynomial growth? Can one decide for a given rational set which of the two options holds?

We give a positive answer to all the previous questions in the case that M is a direct product of free monoids. Some of the proved results also extend to trace monoid.     

Algorithms for Matrix Groups and the Tits Alternative

Tits has shown that a finitely generated matrix group either contains a nonabelian free group or has a solvable subgroup of finite index. We give a polynomial time algorithm for deciding which of these two conditions holds for a given finitely generated matrix group over an algebraic number field. Noting that many computational problems are undecidable for groups with nonabelian free subgroups, we investigate the complexity of problems relating to matrix groups with solvable subgroups of finite index. For such a groupG, we are able in polynomial time to compute a homomorphismφsuch thatφ(G) is a finite matrix group and the kernel ofφis solvable. If, in addition,Ghas a nilpotent subgroup of finite index, we obtain much stronger results. For such groups, we show how to effectively compute an encoding of elements ofGsuch that the encoding length of an element obtained as a product of length ⩽ℓ over the generators isO(log ℓ) times a polynomial in the input length. This result is the best possible; it has been shown by Tits and Wolf that if a finitely generated matrix group does not have a nilpotent subgroup of finite index, then the number of group elements expressible as words of length ℓ over the generators grows asc^ℓfor some constantc>1 depending onG. For groups with abelian subgroups of finite index, we obtain a Las Vegas algorithm for several basic computational tasks, including membership testing and computing a presentation. This generalizes recent work of Beals and Babai, who give a Las Vegas algorithm for the case of finite groups, as well as recent work of Babai, Beals, Cai, Ivanyos, and Luks, who give a deterministic algorithm for the case of abelian groups.     

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     

On the lengths of values in a finite transducer

We investigate finite transducers and their inner structure with regard to the lengths of values. Our transducer models are the normalized finite transducer (NFT) and the nondeterministic generalized sequential machine (NGSM), which is a real-time NFT. The length-degree of an NFT is defined to be the maximal number of different lengths of values for an input word or is infinite, depending on whether or not a maximum exists. We show: An NGSMM with finite length-degree can be effectively decomposed into finitely many NGSMsM ₁, ...,M _N having length-degree at most 1 such that the transduction realized byM is the union of the transductions realized byM ₁, ...,M _N. Using this decomposition, the equivalence of NGSMs with finite length-degree is recursively decidable. Whether or not an NGSM has finite length-degree can be decided in deterministic polynomial time. By reduction, all these results can be generalized to NFTs.     

A note on a special one-rule semi-Thue system

We show that the special semi-Thue system S₁ = {(abba, λ)} has no equivalent finite semi-Thue system which is uniquely terminating, i.e. canonical. This gives another example of a Thue system with a decidable word problem, but solving it using a canonical string rewriting system is possible only by introducing new additional symbols. In contrast to the example obtained recently by Kapur and Narendran (1984) this system presents a monoid which is in fact a group.     

Decidable sentences of Church-Rosser congruences

A decision procedure for a class of true sentences of congruences generated by finite monadic Church-Rosser systems is developed. Using this decision procedure it is shown that if $\text{M}$_T is the monoid presented by such a system T, then (i) it is decidable given T whether $\text{M}$_T is a group, (ii) it is decidable given T and a finite set A whether the submonoid generated by A is a group or a left (right, two-sided) ideal, and (iii) Green's relations for $\text{M}$_T are decidable.     

Infinite Convergent String-rewriting Systems and Cross-sections for Finitely Presented Monoids

A finitely presented monoid has a decidable word problem if and only if it can be presented by some left-recursive convergent string-rewriting system if and only if it has a recursive cross-section. However, regular cross-sections or even context-free cross-sections do not suffice. This is shown by presenting examples of finitely presented monoids with decidable word problems that do not admit regular cross-sections, and that, hence, cannot be presented by left-regular convergent string-rewriting systems. Also examples of finitely presented monoids with decidable word problems are presented that do not even admit context-free cross-sections. On the other hand, it is shown that each finitely presented monoid with a decidable word problem has a finite presentation that admits a cross-section which is a Church–Rosser language. Finally we address the notion of left-regular convergent string-rewriting systems that are tractable.     

Some non finitely generated monoids of repetition-free endomorphisms

We answer a question raised by Mitrana in Information Processing Letters 64 about primitive morphisms, that is, morphisms that preserve primitiveness of words. Given an alphabet A with Card(A)?2, the monoid of primitive endomorphisms on A and the monoid of primitive uniform endomorphisms on A are not finitely generated. Moreover we show that it is also the case for the following monoids: the monoid of overlap-free (uniform) endomorphisms on A (when Card(A)?3), the monoid of k-power-free (uniform) endomorphisms on A (when Card(A)?2 and k?3).     

Semigroup homomorphisms and fuzzy automata

A generalized Ω-fuzzy automaton over a complete residuated lattice Ω and a monoid (M,*) and with a set S of states is introduced as a monoid homomorphism F:(M,*)→(?,°), where (?,°) is a monoid of Ω-fuzzy sets in a set S×S. An extension principle depending of proper filters Φ in Ω is introduced which then enables to introduce morphisms between generalized Ω-fuzzy automata and to introduce the category ?_Φ of these automata. It is proved that categories of classical fuzzy automata, non-deterministic automata and some other systems are equivalent to subcategories of ?_Φ for a suitable filter Φ.     

Sur le monoide syntactique de L1 lorsque L est un langage fini

We prove that for every finite monoid M, there exists a finite language L so that M divides the syntactic monoid of L¹. Moreover, one can choose for L a full finite prefix code. The same result for finite group has already been proved by Schützenberger. This result is crucial in the proof of the J.-F. Perrot's theorem that the only variety closed under star operation is the variety of all rational languages.     

Monomial Orderings,Rewriting Systems,and Gröbner Bases for the Commutator Ideal of a Free Algebra

In this paper we consider a free associative algebra on three generators over an arbitrary fieldK. Given a term ordering on the commutative polynomial ring on three variables overK, we construct uncountably many liftings of this term ordering to a monomial ordering on the free associative algebra. These monomial orderings are total well orderings on the set of monomials, resulting in a set of normal forms. Then we show that the commutator ideal has an infinite reduced Gröbner basis with respect to these monomial orderings, and all initial ideals are distinct. Hence, the commutator ideal has at least uncountably many distinct reduced Gröbner bases. A Gröbner basis of the commutator ideal corresponds to a complete rewriting system for the free commutative monoid on three generators; our result also shows that this monoid has at least uncountably many distinct minimal complete rewriting systems.The monomial orderings we use are not compatible with multiplication, but are sufficient to solve the ideal membership problem for a specific ideal, in this case the commutator ideal. We propose that it is fruitful to consider such, more general, monomial orderings in non-commutative Gröbner basis theory.     

L-fuzzy grammars

An L-fuzzy grammar is defined by assigning the element of lattice to the rewriting rules of a formal grammar. According to the kind of lattice, say, distributive lattice, lattice-ordered group, and lattice-ordered monoid, two type of L-fuzzy grammars are defined. It is shown that some context-sensitive languages can be generated by type 3 $\text{1-L-}\text{fuzzy}$ grammars with cut points. It is also shown that for type 2 L-fuzzy grammars, Chomsky and Greibach normal form can be constructed as an extension of corresponding notion in the theory of formal grammars.     

A generalization of the Schützenberger product of finite monoids

For each n?1, an n-ary product ? on finite monoids is constructed. This product has the following property: Let Σ be a finite alphabet and Σ¹ the free monoid generated by Σ. For i = 1, …,n, let A_i be a recognizable subset of Σ¹, M(A_i) the syntactic monoid of A_n and M(A₁?A_n) the syntactic monoid of the concatenation product A₁?A_n. Then M(A₁?A_n)< ? (M(A₁),…,M(A_n)). The case n = 2 was studied by Schützenberger. As an application of the generalized product, I prove the theorem of Brzozowski and Knast that the dot-depth hierarchy of star-free sets is infinite.     

Complexity of certain decision problems about congruential languages

Given an arbitrary finite Church-Rosser Thue system S, it is shown that the question of whether a given congruence class is finite is undecidable, and the question of whether every congruence class is finite is not even semidecidable (in fact, Π₂-complete). It is shown that the question of whether a given (resp. every) congruence class is a context-free language is at least as hard. Also, given a finite rewriting system over a commutative monoid, the question of whether every congruence class is finite is shown to be tractable. This contrasts with the known result that the question of whether a given congruence class is finite requires space at least exponential in the square root of the input length.