Abstract
The paper presents combinatorial criteria for confluence of one-rule trace-rewriting systems. The criteria are based on self-overlaps of traces, which are closely related to the notion of conjugacy of traces, and can be tested in linear time. As a special case, we reobtain the corresponding results for strings.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. Book, Confluent and other types of Thue systems,J. Assoc. Comput. Mach. 29 (1982), 171–182.
R. Book, A note on special Thue systems with a single defining relation,Math. Systems Theory 16 (1983), 57–60.
R. Book and H.-N. Liu, Word problems and rewriting in a free partially commutative monoid,Inform. Process. Lett. 26 (1987), 29–32.
R. Book and C. O'Dunlaing, Testing for the Church-Rosser property,Theoret. Comput Sci. 16 (1981), 223–229.
M. Clerbout and M. Latteux, Partial commutations and faithful rational transductions,Theoret. Comput. Sci. 35 (1985), 241–254.
R. Cori and Y. Métivier, Recognizable subsets of some partially abelian monoids,Theoret. Comput. Sci. 35 (1985), 179–189.
R. Cori and D. Perrin, Automates et commutations partielles,RAIRO Inform. Théor. 19 (1985), 21–32.
M. Dauchet, Termination of rewriting is undecidable in the one rule case,Proc. MFCS, Lecture Notes in Computer Science, Vol. 324, Springer-Verlag, Berlin, 1988, pp. 262–268.
N. Dershowitz and J.-P. Jouannaud, Rewrite systems, inFormal Models and Semantics (J. van Leeuwen, ed.), Handbook of Theoretical Computer Science, Vol. B, Eisevier, Amsterdam, 1990, pp. 243–320.
V. Diekert, On the Knuth-Bendix completion for concurrent processes,Proc. ICALP, Lecture Notes in Computer Science, Vol. 267, Springer-Verlag, Berlin, 1987, pp. 42–53.
V. Diekert,Combinatorics on Traces, Lecture Notes in Computer Science, Vol. 454, Springer-Verlag, Berlin, 1990.
C. Duboc, On some equations in free partially commutative monoids,Theoret. Comput. Sci. 46 (1986), 159–174.
G. Huet, Confluent reductions: abstract properties and applications to term rewriting systems,J. Assoc. Comput. Mach. 27 (1980), 797–821.
M. Jantzen,Confluent String Rewriting, EATCS Monographs on Theoretical Computer Science, Vol. 14, Springer-Verlag, New York, 1988.
W. Kurth, Termination und Confluenz von Semi-Thue-Systems mit nur einer Regel, Dissertation, Mathematisch-Naturwissenschaftliche Fakultät, Technische Universität Clausthal, 1990, Kapitel 6.
H.-N. Liu, C. Wrathall, and K. Zeger, Efficient solution of some problems in free partially commutative monoids,Inform, and Comput. 89 (1990), 180–198.
M. Lothaire,Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.
Y. Métivier, Calcul de longeurs de chaines de reecriture dans la monoide libre,Theoret. Comput. Sci. 35 (1985), 71–87.
P. Narendran and R. McNaughton, The undecidability of the preperfectness of Thue systems,Theoret. Comput. Sci. 31 (1984), 165–174.
P. Narendran and F. Otto, Preperfectness is undecidable for Thue systems containing only length-reducing rales and a single commutation rule,Inform. Process. Lett. 29 (1988), 125–130.
F. Otto, On deciding confluence of finite string-rewriting systems modulo partial commutativity,Theoret. Comput. Sci. 67 (1989), 19–35.
F. Otto, On confluence versus strong confluence for one-rule trace-rewriting systems,Math. Systems Theory, this issue, pp. 363–384.
F. Otto and C. Wrathall, A note on Thue systems with a single defining relation,Math. Systems Theory 18 (1985), 135–143.
F. Otto and C. Wrathall, Characterizations of Overlaps in Free Partially Commuative Monoids, Interner Bericht 184/88, Fachbereich Informatik, Universität Kaiserslautem, 1988.
F. Otto and C. Wrathall, Overlaps in free partially commutative monoids,J. Comput. System Sci. 42 (1991), 186–198.
C. Wrathall, Confluence of one-rule Thue systems, inWord Equations and Related Topics (K. U. Schulz, ed.), Lecture Notes in Computer Science, Vol. 572, Springer-Verlag, Berlin, 1992, pp. 237–246.
Author information
Authors and Affiliations
Additional information
The work of the second author was supported in part by the EBRA working goup No. 3166 ASMICS.
Rights and permissions
About this article
Cite this article
Wrathall, C., Diekert, V. On confluence of one-rule trace-rewriting systems. Math. Systems Theory 28, 341–361 (1995). https://doi.org/10.1007/BF01185401
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01185401