Thue systems as rewriting systems

1. S. Adjan, Defining relations and algorithmic problems for groups and semigroups, Proc. Steklov Inst. Math. 85, 1966. (English version published by the American Mathematical Society, 1967.)

   Google Scholar 

2. J. Avenhaus, R. Book, and C. Squier, On expressing commutativity by Church-Rosser presentations: a note on commutative monoids, R.A.I.R.O. Informatique Théorique 18 (1984), 47–52.

   Google Scholar 

3. J. Avenhaus and K. Madlener, Algorithmische probleme bei einrelatorgruppen und ihre komplexität, Arch. Math. Logic 19 (1978), 3–12.

   Google Scholar 

4. J. Avenhaus, K. Madlener, and F. Otto, Groups presented by finite two-monadic Church-Rosser Thue systems, Interner Bericht, Fachbereich Informatik, Univ. Kaiserslautern, 1984.

   Google Scholar 

5. G. Bauer, Zur Darstellung von Monoiden durch Regelsysteme, Dissertation, Univ. Kaiserslautern, 1984.

   Google Scholar 

6. G. Bauer, N-level rewriting systems, submitted for publication.

   Google Scholar 

7. G. Bauer and F. Otto, Finite complete rewriting systems and the complexity of the word problem, Acta Informatica 21 (1984) 521–540.

   Google Scholar 

8. J. Berstel, Congruences plus que parfaites et langages algébriques, Séminaire d'Informatique Théorique, Institut de Programmation, 1976–77, 123–147.

   Google Scholar 

9. R. Book, Confluent and other types of Thue systems, J. Assoc. Computing Mach. 29 (1982), 171–183.

   Google Scholar 

10. R. Book, When is a monoid a group? The Church-Rosser case is tractable, Theoret. Comput. Sci. 18 (1982), 325–331.

    Google Scholar 

11. R. Book, A note on special Thue systems with a single defining relation, Math. Systems Theory 16 (1983), 301–312.

    Google Scholar 

12. R. Book, Decidable questions of Church-Rosser congruences, Theoret. Comput. Sci. 24 (1983), 301–312.

    Google Scholar 

13. R. Book, Homogeneous Thue systems and the Church-Rosser property, Discrete Math. 48 (1984), 137–145.

    Google Scholar 

14. R. Book, M. Jantzen, and C. Wrathall, Monadic Thue systems, Theoret. Comput. Sci. 19 (1982), 231–251.

    Google Scholar 

15. R. Book and C. O'Dúnlaing, Thue congruences and the Church-Rosser property, Semigroup Forum 22 (1981), 325–331.

    Google Scholar 

16. R. Book and C. O'Dúnlaing, Testing for the Church-Rosser property, Theoret. Comput. Sci. 16(1981), 223–229.

    Google Scholar 

17. R. Book and F. Otto, Cancellation rules and extended word problems, Information Proc. Letters 20 (1985), 5–11.

    Google Scholar 

18. R. Book and F. Otto, On the security of two-party name-stamp protocols, Theoret. Comput. Sci., to appear.

    Google Scholar 

19. R. Book and F. Otto, On the verifiability of two-party algebraic protocols, Theoret. Comput. Sci., to appear.

    Google Scholar 

20. R. Book and C. Squier, Almost all one-rule Thue systems have decidable word problems, Discrete Math. 49 (1984), 237–240.

    Google Scholar 

21. Y. Cochet, Sur l'algébricité des classes de certaines congruences définés sur le monoide libre. Thèse 3^eme cycles, Rennes, 1971.

    Google Scholar 

22. Y. Cochet, Church-Rosser congruences on free semigroups, Collog. Math. Soc. Janos Bolyai: Algebraic Theory of Semigroups 20 (1976), 51–60.

    Google Scholar 

23. Y. Cochet and M. Nevat, Une généralization des ensembles de Dyck, Israel J. Math. 9 (1971), 389–395.

    Google Scholar 

24. D. Dolev and A. Yao, On the security of public-key protocols, IEEE Trans. Information Theory IT-22 (1976), 644–654.

    Google Scholar 

25. R. Gilman, Computations with rational subsets of confluent groups, in J. Fitch (ed.), EUROSAM 1984, Lecture Notes in Computer Science 174 (1984), 207–212.

    Google Scholar 

26. G. Huet, Confluent reductions: abstract properties and applications to term-rewriting systems, J. Assoc. Comput. Mach. 27 (1980), 797–821.

    Google Scholar 

27. G. Huet and D. Oppen, Equations and rewrite rules, in R. Book (ed.), Formal Language Theory: Perspectives and Open Problems, Academic Press, 1980, 349–405.

    Google Scholar 

28. M. Jantzen, On a special monoid with a single defining relation, Theoret. Comput. Sci. 16 (1981), 61–73.

    Google Scholar 

29. D. Kapur, M. Krishnamoorthy, R. McNaughton, and P. Narendran, An O(|T|³) algorithm for testing the Church-Rosser property of Thue systems, Theoret. Comput. Sci., 35 (1985), 109–114.

    Google Scholar 

30. D. Kapur and P. Narendran, A finite Thue system with decidable word problem and without equivalent finite canonical system, Theoret. Comput. Sci., 35 (1985), 337–344.

    Google Scholar 

31. D. Kapur and P. Narendran, The Knuth-Bendix completion procedure and Thue systems, SIAM J. Computing, to appear.

    Google Scholar 

32. D. Knuth and P. Bendix, Simple word problems in universal algebras, in J. Leech (ed.), Computational Problems in Abstract Algebra, Pergamon Press, 1970, 263–297.

    Google Scholar 

33. K. Madlener and F. Otto, Pseudo-natural algorithms for decision problems in certain types of string-rewriting systems, submitted for publication.

    Google Scholar 

34. W. Magnus, A. Karrass, and D. Solitar, Combinatorial Group Theory, Wiley-Interscience, 1966.

    Google Scholar 

35. Y. Metivier, Calcul de longuerurs de chaines de reecriture dans le monoide libre, Theoret. Comput. Sci. 35 (1985), 71–88.

    Google Scholar 

36. D. Muller and P. Schupp, Groups, the theory of ends, and context-free languages, J. Comput. System Sci. 26 (1983), 295–310.

    Google Scholar 

37. P. Narendran, Church-Rosser and Related Thue systems, Ph.D. Dissertation, Rennesselaer Poly. Institute, 1983. Also appears as Report No. 84CRD176, General Electric Corporate Research and Development Center, Schenectady, NY, 1984.

    Google Scholar 

38. M. Nivat (avec M. Benois), Congruences parfaites, Seminaire Dubriels, 25^e Année, 1971–72, 7-01-09.

    Google Scholar 

39. C. O'Dúnlaing, Finite and Infinite Regular Thue Systems, Ph.D. Dissertation, Univ. of California at Santa Barbara, 1981.

    Google Scholar 

40. C. O'Dúnlaing, Infinite regular Thue systems, Theoret. Comput. Sci., 25 (1983), 339–345.

    Google Scholar 

41. C. O'Dúnlaing, Undecidable questions of Thue systems, Theoret. Comput. Sci., 23 (1983), 339–345.

    Google Scholar 

42. F. Otto, Some undecidability results for non-monadic Church-Rosser Thue systems, Theoret. Comput. Sci., 33 (1984), 261–278.

    Google Scholar 

43. F. Otto, Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group, Theoret. Comput. Sci., 32 (1984), 249–260.

    Google Scholar 

44. F. Otto, Church-Rosser Thue systems that present free monoids, SIAM J. Computing, to appear.

    Google Scholar 

45. F. Otto, Elements of finite order for finite monadic Church-Rosser Thue systems, Trans. American Math. Soc., to appear.

    Google Scholar 

46. F. Otto, Deciding algebraic properties of monoids presented by finite Church-Rosser Thue systems, Proc. First International Conference on Rewriting Techniques and Applications, Dijon, France, May 1985, Lecture Notes in Computer Science, to appear.

    Google Scholar 

47. F. Otto, Decision Problems and their Complexity for Monadic Church-Rosser Thue Systems, in preparation.

    Google Scholar 

48. F. Otto, and C. Wrathall, A note on Thue systems with a single defining relation, Math. Systems Theory, to appear.

    Google Scholar 

49. L. Pan, On reduced Thue systems, Math. Systems Theory, to appear.

    Google Scholar 

50. L. Pan, On the security of p-party protocols, submitted for publication.

    Google Scholar 

51. D. Perrin and P. Schupp, Sure les monoids à un relateur qui sont des groupes, Theoret. Comput. Sci., 33 (1984), 331–334.

    Google Scholar 

52. D. Potts, Remarks on an example of Jantzen, Theoret. Comput. Sci., 29 (1984), 277–284.

    Google Scholar 

53. C. Squier, personal communication.

    Google Scholar 

54. C. Squier and C. Wrathall, A note on representations of a certain monoid, Theoret. Comput. Sci., 17 (1982), 229–231.

    Google Scholar 

55. A. Thue, Probleme über Veranderungen von Zeichenreihen nach gegeben Regeln, Skr. Vid. Kristianaia, I. Mat. Naturv. Klasse, No. 10 (1914), 34 pp.

    Google Scholar 

56. C. Wrathall, On monoids and groups, in preparation.

    Google Scholar 

Download references