×

Confluence problems for trace rewriting systems. (English) Zbl 1007.68088

Summary: Rewriting systems over trace monoids, briefly trace rewriting systems, generalize both semi-Thue systems and vector replacement systems. Previously, a particular trace monoid \(M\) was presented such that confluence is undecidable for the class of length-reducing trace rewriting systems over \(M\). In this paper, we show that this result holds for every trace monoid, which is neither free nor free commutative. Furthermore we show that confluence for special trace rewriting systems over a fixed trace monoid is decidable in polynomial time.

MSC:

68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bauer, G.; Otto, F., Finite complete rewriting systems and the complexity of the word problem, Acta Inform., 21, 521-540 (1984) · Zbl 0535.68019
[2] Berstel, J, and, Perrin, D. 1985, Theory of Codes, Academic Press, San Diego.; Berstel, J, and, Perrin, D. 1985, Theory of Codes, Academic Press, San Diego. · Zbl 0587.68066
[3] Bertol, M. 1996, Effiziente Normalform-Algorithmen für Ersetzungssysteme über partiell kommutativen Monoiden, Ph.D. thesis, Universität Stuttgart.; Bertol, M. 1996, Effiziente Normalform-Algorithmen für Ersetzungssysteme über partiell kommutativen Monoiden, Ph.D. thesis, Universität Stuttgart. · Zbl 0874.68109
[4] Bertol, M., and Diekert, V.1995, On efficient reduction-algorithms for some trace rewriting systems, in; Bertol, M., and Diekert, V.1995, On efficient reduction-algorithms for some trace rewriting systems, in
[5] Bertol, M., and Diekert, V.1996, Trace rewriting: Computing normal forms in time \(Onn in \); Bertol, M., and Diekert, V.1996, Trace rewriting: Computing normal forms in time \(Onn in \) · Zbl 1379.68193
[6] Bertoni, A.; Mauri, G.; Sabadini, N., Membership problems for regular and context free trace languages, Inform. and Comput., 82, 135-150 (1989) · Zbl 0682.68040
[7] Book, R, and, Otto, F. 1993, String-Rewriting Systems, Springer-Verlag, Berlin.; Book, R, and, Otto, F. 1993, String-Rewriting Systems, Springer-Verlag, Berlin. · Zbl 0832.68061
[8] Book, R. V.; O’Dunlaing, C. P., Testing for the Church-Rosser property (note), Theoret. Comput. Sci., 16, 223-229 (1981) · Zbl 0479.68035
[9] Cori, R.; Perrin, D., Automates et commutations partielles, RAIRO Inform. Théor. Appl., 19, 21-32 (1985) · Zbl 0601.68055
[10] Diekert, V.1987, On the Knuth-Bendix completion for concurrent processes, in; Diekert, V.1987, On the Knuth-Bendix completion for concurrent processes, in · Zbl 0633.68015
[11] Diekert, V.1990, Combinatorial rewriting on traces, in; Diekert, V.1990, Combinatorial rewriting on traces, in · Zbl 0729.68034
[12] Diekert, V. 1990, Combinatorics on Traces, Lecture Notes in Computer Science, Vol, 454, Springer-Verlag, Berlin.; Diekert, V. 1990, Combinatorics on Traces, Lecture Notes in Computer Science, Vol, 454, Springer-Verlag, Berlin.
[13] Diekert, V., Word problems over traces which are solvable in linear time, Theoret. Comput. Sci., 74, 3-18 (1990) · Zbl 0701.68056
[14] Diekert, V, and, Rozenberg, G. Eds, 1995, The Book of Traces, World Scientific, Singapore.; Diekert, V, and, Rozenberg, G. Eds, 1995, The Book of Traces, World Scientific, Singapore.
[15] Huet, G, and, Lankford, D. 1978, On the Uniform Halting Problem for Term Rewriting Systems, Report Lab. Report 283, INRIA, Le Chesnay, France.; Huet, G, and, Lankford, D. 1978, On the Uniform Halting Problem for Term Rewriting Systems, Report Lab. Report 283, INRIA, Le Chesnay, France.
[16] Jantzen, M. 1988, Confluent String Rewriting, EATCS Monographs on Theoretical Computer Science, Vol, 14, Springer-Verlag, Berlin.; Jantzen, M. 1988, Confluent String Rewriting, EATCS Monographs on Theoretical Computer Science, Vol, 14, Springer-Verlag, Berlin. · Zbl 1097.68572
[17] Kapur, D.; Krishnamoorthy, M. S.; McNaughton, R.; Narendran, P., An \(O(|T|^3)\) algorithm for testing the Church-Rosser property of Thue systems, Theoret. Comput. Sci., 35, 109-114 (1985) · Zbl 0563.03018
[18] Lohrey, M.1998, On the confluence of trace rewriting systems, in; Lohrey, M.1998, On the confluence of trace rewriting systems, in
[19] Lohrey, M.1999, Complexity results for confluence problems. in; Lohrey, M.1999, Complexity results for confluence problems. in · Zbl 0955.68063
[20] Mazurkiewicz, A. 1977, Concurrent Program Schemes and Their Interpretations, DAIMI Rep. PB 78, Aarhus University, Aarhus.; Mazurkiewicz, A. 1977, Concurrent Program Schemes and Their Interpretations, DAIMI Rep. PB 78, Aarhus University, Aarhus.
[21] Narendran, P.; Otto, F., Preperfectness is undecidable for Thue systems containing only length-reducing rules and a single commutation rule, Inform. Process. Lett., 29, 125-130 (1988) · Zbl 0653.03026
[22] Newman, M. H.A., On theories with a combinatorial definition of “equivalence”, Ann. of Math., 43, 223-243 (1943) · Zbl 0060.12501
[23] Nivat, M.; Benois, M., Congruences parfaites et quasi-parfaites, Semi. Dubreil, 25 (1971/1972) · Zbl 0338.02018
[24] Verma, R. M., Rusinowitch, M., and Lugiez, D.1998, Algorithms and reductions for rewriting problems, in; Verma, R. M., Rusinowitch, M., and Lugiez, D.1998, Algorithms and reductions for rewriting problems, in · Zbl 0989.03036
[25] Wrathall, C.1992, Confluence of one-rule Thue systems, in; Wrathall, C.1992, Confluence of one-rule Thue systems, in
[26] Wrathall, C.; Diekert, V., On confluence of one-rule trace-rewriting systems, Math. Systems Theory, 28, 341-361 (1995) · Zbl 0837.68055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.