×

The word problem for \(1\mathcal{LC}\) congruences is NP-hard. (English) Zbl 1059.68077

Summary: It is proved that the word problem for congruences generated by subsets of \[ \{(abc,acb) \mid a \in A \cup \{\varepsilon\},b,c \in A\} \] is NP-hard. These congruences are a generalization of Mazurkiewicz’s traces.

MSC:

68R05 Combinatorics in computer science
68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aalbersberg, I. J.; Rozenberg, G., Theory of traces, Theoret. Comput. Sci., 60, 1, 1-90 (1988) · Zbl 0652.68017
[2] Adyan, S. I., Defining relations and algorithmic problems for groups and semigroups, Tr. Mat. Inst. Steklov Akad. Nauk SSSR, 85, 1-90 (1966) · Zbl 0204.01702
[3] Adyan, S. I., Transformations of words in a semigroup presented by a system of defining relations, Algebra i Logika, 15, 6, 611-621 (1976) · Zbl 0368.20037
[4] Adyan, S. I.; Oganesyan, G. U., On the word and divisibility problems in semigroups with a single defining relation, Izvestija Akad. Nauk SSSR Ser. Math., 42, 2, 219-225 (1978) · Zbl 0389.20047
[5] I. Biermann, Extensions structurelles des traces de commutation, Thèse de Doctorat, Université Paris-Sud, Orsay, France, 1995.; I. Biermann, Extensions structurelles des traces de commutation, Thèse de Doctorat, Université Paris-Sud, Orsay, France, 1995.
[6] I. Biermann, B. Rozoy, Context Traces and Transition Systems, in: Proc. of the 9th Internat. Symp. on Computers and Information Science, Antalya, Turkey (ISCIS IX) printed at Boğaziçi University, 1994, pp. 301-309.; I. Biermann, B. Rozoy, Context Traces and Transition Systems, in: Proc. of the 9th Internat. Symp. on Computers and Information Science, Antalya, Turkey (ISCIS IX) printed at Boğaziçi University, 1994, pp. 301-309.
[7] I. Biermann, L. Rosaz, B. Rozoy, Occurrence preserving congruences and associated graphs, Theoret. Informatics Appl. (former RAIRO), to appear.; I. Biermann, L. Rosaz, B. Rozoy, Occurrence preserving congruences and associated graphs, Theoret. Informatics Appl. (former RAIRO), to appear.
[8] Cartier, P.; Foata, D., Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics, Vol. 85 (1969), Springer: Springer Berlin · Zbl 0186.30101
[9] M. Clerbout, Commutations partielles et familles de langages, Thèse de doctorat, Université des Sciences et Technologies de Lille, France, 1984.; M. Clerbout, Commutations partielles et familles de langages, Thèse de doctorat, Université des Sciences et Technologies de Lille, France, 1984.
[10] Clerbout, M.; Latteux, M., Semi-commutations, Inform. and Comput., 73, 59-74 (1987) · Zbl 0629.68078
[11] V. Diekert, On the concatenation of infinite traces, in: Proc. of 8th Symp. on Theoretical Aspects of Computer Science, (STACS’91), Lecture Notes in Computer Science, Vol. 480, Springer Berlin, pp. 105-117.; V. Diekert, On the concatenation of infinite traces, in: Proc. of 8th Symp. on Theoretical Aspects of Computer Science, (STACS’91), Lecture Notes in Computer Science, Vol. 480, Springer Berlin, pp. 105-117. · Zbl 0773.68057
[12] V. Diekert, P. Gastin, A. Petit, Recognizable complex trace languages, in: Proc. of the 16th Symp. on Mathematical Foundations of Computer Science (MFCS’91), Lecture Notes in Computer Science, Vol. 520, Springer, Berlin, pp. 131-140.; V. Diekert, P. Gastin, A. Petit, Recognizable complex trace languages, in: Proc. of the 16th Symp. on Mathematical Foundations of Computer Science (MFCS’91), Lecture Notes in Computer Science, Vol. 520, Springer, Berlin, pp. 131-140. · Zbl 0777.68057
[13] Diekert, V.; Rozenberg, G., The Book of Traces (1995), World Scientific Publ. Co: World Scientific Publ. Co Singapore
[14] Gastin, P., Un modèle asynchrone pour les systèmes distribués, Theoret. Comput. Sci., 74, 2, 121-162 (1990) · Zbl 0701.68023
[15] Gastin, P.; Rozoy, B., The Poset of infinitary traces, Theoret. Comput. Sci., 120, 1, 101-121 (1993) · Zbl 0787.68056
[16] P. Hoogers, Behavioral aspects of Petri nets, Ph.D. Thesis, Rijksuniversiteit, Leiden, Netherlands, 1994.; P. Hoogers, Behavioral aspects of Petri nets, Ph.D. Thesis, Rijksuniversiteit, Leiden, Netherlands, 1994.
[17] P. Hoogers, H.C.M. Kleijn, P.S. Thiagarajan, A trace semantics for petri nets, in: Proc. of the 19th Internat. Coll. on Automata, Languages and Programming (ICALP’92), Lecture Notes in Computer Science, Vol. 623, Springer, Berlin, pp. 595-604.; P. Hoogers, H.C.M. Kleijn, P.S. Thiagarajan, A trace semantics for petri nets, in: Proc. of the 19th Internat. Coll. on Automata, Languages and Programming (ICALP’92), Lecture Notes in Computer Science, Vol. 623, Springer, Berlin, pp. 595-604. · Zbl 0826.68085
[18] Kwiatkowska, M. Z., On Infinitary Trace Languages (1989), University of Leicester: University of Leicester England
[19] Lacaze, J., Parties reconnaissables de monoı̈des définis par Générateurs et Relations, Theoret. Informatics Appl. (former RAIRO), 26, 6, 541-552 (1992) · Zbl 0784.68050
[20] G. Lallement, The Word Problem for Thue Rewriting Systems, French Spring School of Theoretical Computer Science, Term Rewriting, Lecture Notes in Computer Science, Vol. 909, Springer, Berlin, 1993, pp. 27-38.; G. Lallement, The Word Problem for Thue Rewriting Systems, French Spring School of Theoretical Computer Science, Term Rewriting, Lecture Notes in Computer Science, Vol. 909, Springer, Berlin, 1993, pp. 27-38.
[21] Magnus, W., Das Identitätsproblem für Gruppen mit einer definierenden Relation, Math. Ann., 106, 295-307 (1932) · Zbl 0004.09709
[22] A.A. Markov, On the impossibility of certain algorithms in the theory of associative systems, Dokl. Akad. Nauk SSSR 55 (1947) 587-590; A.A. Markov, Doklady Akad. Nauk SSSR 58 (1947) 353-356.; A.A. Markov, On the impossibility of certain algorithms in the theory of associative systems, Dokl. Akad. Nauk SSSR 55 (1947) 587-590; A.A. Markov, Doklady Akad. Nauk SSSR 58 (1947) 353-356.
[23] A.A. Markov, Theory of Algorithms, Tr. Mat. Inst. Akad. Nauk SSSR 42, 1956, Chapter 5, Sections 4 and 5.; A.A. Markov, Theory of Algorithms, Tr. Mat. Inst. Akad. Nauk SSSR 42, 1956, Chapter 5, Sections 4 and 5.
[24] Yu.V. Matiyasevich, Simple examples of unsolvable associative calculi, Dokl. Akad. Nauk SSSR 173 (6) (1967) 1264-126; Tr. Math Inst. Steklov Akad. Nauk SSSR, 93 50-88.; Yu.V. Matiyasevich, Simple examples of unsolvable associative calculi, Dokl. Akad. Nauk SSSR 173 (6) (1967) 1264-126; Tr. Math Inst. Steklov Akad. Nauk SSSR, 93 50-88.
[25] A. Mazurkiewicz, Concurrent program schemes and their interpretations Aarhus University, DAIMI Report PB 78, 1977.; A. Mazurkiewicz, Concurrent program schemes and their interpretations Aarhus University, DAIMI Report PB 78, 1977.
[26] A. Mazurkiewicz, Trace theory, in: Proc. of an Advanced Course in Petri Nets, Lecture Notes in Computer Science, Vol. 255, Springer, Berlin, 1986, pp. 279-324.; A. Mazurkiewicz, Trace theory, in: Proc. of an Advanced Course in Petri Nets, Lecture Notes in Computer Science, Vol. 255, Springer, Berlin, 1986, pp. 279-324.
[27] Oganesyan, G. U., On the problems of equality and divisibility of words in a semigroup with a defining relation of the form \(a= bA \), Izvestija Akad. Nauk SSSR Ser. Math., 42, 3, 602-612 (1978) · Zbl 0385.20029
[28] Post, E. L., Recursive unsolvability of a problem of Thue, J. Symbolic Logic, 12, 1-11 (1947) · Zbl 1263.03030
[29] Reisig, W., Petrinets, an introduction, EATCS Monographs of TCS, Vol. 4 (1985), Springer: Springer Berlin
[30] Tzeitin, G. C., Associative calculus with an unsolvable equivalence problem, Tr. Math. Inst. Steklov Akad. Nauk SSSR, 52, 172-189 (1958)
[31] Vogler, W., A generalization of traces, Theoret. Informatics Appl. (former RAIRO), 25, 2, 147-156 (1991) · Zbl 0731.68083
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.