A test for λ-confluence for certain prefix rewriting systems with applications to the generalized word problem

ABSTRACT

We apply rewriting techniques to the generalized word problem for groups. Let R be a finite string-rewriting system on an alphabet &Sgr; such that the monoid MR presented by (&Sgr;:R) is a group, and let U ⊆ &Sgr;→ be a finite set. The generalized word problem GWP is defined by GWP(w.U) if w ∈ <U>, where <U> is the subgroup of MR generated by U. With U we associate a prefix rewriting relation ⇒P on &Sgr;* such that w &if;P &lgr; if GWP(w.U) holds. If ⇒P is &lgr;-confluent then w ⇒ P &lgr; if w ∈ <U>. Then ⇒P yields a decision procedure for GWP. For groups given through confluent string-rewriting systems R, we develop a necessary and sufficient condition for ⇒P being &lgr;-confluent and show that this condition becomes decidable in case of R being length-reducing, in addition.

REFERENCES

• 1: J. Avenhaus. K. Madlener: On groups defined by monadic Thue systems, Algebra. Combinatorics. and Logic in Computer Science, Colloq. Math. Soc. Janos Bolyai. vol. 42. 1983. pp. 63-71.
• 2: Ronald V. Book, Thue systems as rewriting systems, Journal of Symbolic Computation, v.3 n.1-2, p.39-68, Feb./April 1987 [doi>10.1016/S0747-7171(87)80021-4]
• 3: B. BuchJ:~rger. G.E. Collins. R. Loos ~mcls.), Computer Algebra (Symbolic and Algebraic Computation). Computing Supplementum 4. Springer: Wien/New York. 1982. pp. 11-43.
• 4: M. Dehn, Uber endliche diskontinuierliche Gruppen, Math. Ann. ?1 (1911) 116-144.
• 5: R. H. Gilrrtan: Presentations of groups and monoids, J. of Algebra 57 (1979) 544-554.
• 6: T. Harju , J. Karhumäki, Decidability of the multiplicity equivalence of multitape finite automata, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.477-481, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100281]
• 7: D. Knuth. P. Bendix, Simple word problems in universal algebras, in: J. Leech (ed.). Computational Problems in Abstract Algebra. Pergamon: New York. 1970. pp. 263-297.
• 8: N. Kuhn , K. Madlener, A method for enumerating cosets of a group presented by a canonical system, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.338-350, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74580]
• 9: Philippe Le Chenadec, A catalogue of complete group presentations, Journal of Symbolic Computation, v.2 n.4, p.363-381, Dec. 1986 [doi>10.1006/jsco.1995.1055]
• 10: R. Lyndon. P. Schupp, Combinatorial Group Theory~ Springer: Berlin/Heidelberg/New York. 1077.
• 11: K. Madlener , F. Otto, Groups presented by certain classes of finite length-reducing string rewriting systems, on Rewriting techniques and applications, p.133-144, May 1987, Bordeaux, France
• 12: C. F. l~iller. III, On group-theoretic decision problems and their classification, Ann. of Math. Studies 68. Princeton University Press: Princeton. 1971.
• 13: F. Otto, On deciding the confluence of a finite string-rewriting system on a given congruence class, Journal of Computer and System Sciences, v.35 n.3, p.285-310, Dec. 1987 [doi>10.1016/0022-0000(87)90017-1]
• 14: D. WiBn-tann_. Anwendungen von Rewriting- Techniken in polyzyklischen Gruppen: Dissertation. Fachbe re ich Infor matik. Uni verst t~t Kaiserslautern. 1988.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Languages, Theory