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.     

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     

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.     

Rewriting systems and word problems in a free partially commutative monoid

We show that, for finite Thue systems that are confluent modulo the equivalence relation induced by partial commutativity, the word problem is decidable in linear time. In addition, we show that there is a polynomial-time algorithm that on input a finite Thue system will determine whether the Thue system is confluent modulo the equivalence relation induced by partial commutativity.     

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.     

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.     

Procedures for searching local solutions of linear differential systems with infinite power series in the role of coefficients

Construction of Laurent, regular, and formal (exponential–logarithmic) solutions of full-rank linear ordinary differential systems is discussed. The systems may have an arbitrary order, and their coefficients are formal power series given algorithmically. It has been established earlier that the first two problems are algorithmically decidable and the third problem is not decidable. A restricted variant of the third problem was suggested for which the desired algorithm exists. In the paper, a brief survey of algorithms for the abovementioned decidable problems is given. Implementations of these algorithms in the form of Maple procedures with a uniform interface and data representation are suggested.     

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.     

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.     

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?     

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.     

Decision problems for finite special string-rewriting systems that are confluent on some congruence class

The class of decision problems for which finite, special string-rewriting systems that are confluent on some congruence class effectively provide algorithms is compared to the class of decision problems for which finite, monadic, and confluent string-rewriting systems effectively yield algorithms. Among the decision problems solved are the word problem, the power problem, the left-and right-divisibility problems, the finiteness problem, the group problem, the problem of torsion-freeness, the inclusion problem, and the generalized word problem. In particular, it is shown that the technique of linear sentences of Book [7] applies to finite, special string-rewriting systems that are confluent on some congruence class.This work was prepared while the first author was visiting at Fachbereich Informatik, Universität Kaiserslautern, Kaiserslautern, Federal Republic of Germany. Some of the results presented here were first announced at the 8th International Conference on Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Tokyo, Japan, August 1990     

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.     

取值于赋值幺半群的加权正则文法语言

正则文法是研究自动机的重要工具。引入取值于赋值幺半群的加权正则文法、加权类正则文法的定义,讨论了赋值幺半群上加权正则文法、加权类正则文法和加权有限自动机(WFA)的关系。证明了在赋值幺半群上,已知一个加权正则文法或加权类正则文法,分别存在一个WFA与之等价。定义了可分配的赋值幺半群,证明了在可分配的赋值幺半群上已知一个WFA,存在一个加权正则文法和加权类正则文法与之等价,即证明了可分配的赋值幺半群上加权正则文法、加权类正则文法和WFA在生成语言上等价,并举例说明了赋值幺半群的可分配性不是已知WFA存在与之等价的加权正则文法或加权类正则文法的必要条件。     

Two-way counter machines and finite-state transducers†

Consider the emptiness problem for deterministic two-way finite-state automata that are augmented by a bounded-reversal counter and the equivalence problem for deterministic two-way finite-state transducers. The first problem was posed by Ibarra while the second problem restricted to the case that accepting configurations are also halting configurations was posed by Ehrich and Yau. Recently the first problem restricted to devices that accept only bounded languages as well as the restricted version of the second problem have been shown decidable. Here these two problems are shown decidable also in their general form.     

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ω-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.     

String rewriting for double coset systems

In this paper we show how string rewriting methods can be applied to give a new method of computing double cosets. Previous methods for double cosets were enumerative and thus restricted to finite examples. Our rewriting methods do not suffer this restriction and we present some examples of infinite double coset systems which can now easily be solved using our approach. Even when both enumerative and rewriting techniques are present, our rewriting methods will be competitive because they (i) do not require the preliminary calculation of cosets; and (ii) as with single coset problems, there are many examples for which rewriting is more effective than enumeration.Automata provide the means for identifying expressions for normal forms in infinite situations and we show how they may be constructed in this setting. Further, related results on logged string rewriting for monoid presentations are exploited to show how witnesses for the computations can be provided and how information about the subgroups and the relations between them can be extracted. Finally, we discuss how the double coset problem is a special case of the problem of computing induced actions of categories which demonstrates that our rewriting methods are applicable to a much wider class of problems than just the double coset problem.     

Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups

We consider the problem of testing whether a given system of equations over a fixed finite semigroup S has a solution. For the case where S is a monoid, we prove that the problem is computable in polynomial time when S is commutative and is the union of its subgroups but is NP-complete otherwise. When S is a monoid or a regular semigroup, we obtain similar dichotomies for the restricted version of the problem where no variable occurs on the right-hand side of each equation. We stress connections between these problems and constraint satisfaction problems. In particular, for any finite domain D and any finite set of relations Γ over D, we construct a finite semigroup S_Γ such that CSP(Γ) is polynomial-time equivalent to the satifiability problem for systems of equations over S_Γ.     

Picture deformation

Algebraic picture generation based on a pixel deformation theory is presented. The main tool used is the deformation monoid which simulates the algebraic structure of pictures viewed as rectangular arrays with operations the horizontal and vertical concatenation. Picture languages generated by grammatical systems are considered and a Chomsky-like normal form as well as an iteration lemma are established. Infinite pictures are obtained as the ω-completion of the set of finite pictures ordered by picture refinement. Regular fractal pictures (such as the Sierpinski Carpet, the Cantor dust, etc.) are defined as the components of the least solution of systems whose right hand side members are finite pictures. They constitute the least class of pictures containing the finite pictures and closed under substitution and the self similarity operation. Solving non deterministic picture program schemes we get the so called ∞-refinement languages which consist of finite and infinite pictures. For such languages the emptiness and finiteness problems are decidable.