×

The code problem for traces – improving the boundaries. (English) Zbl 0903.68129

Summary: The code problem for traces – given a finite set \(X\), decide whether every element in \(X^{+}\) has a unique factorization over \(X\) – is decidable if the independence relation equals \(P_{4}\), the line graph on four nodes. Additionally, it is undecidable for a particular independence relation that does not have \(C_{4}\), the cycle on four nodes, as induced subgraph. These results improve on the previously known boundaries of (un) decidable cases for this problem.

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aalbersberg, I. J.J.; Hoogeboom, H. J., Characterizations of the decidability of some problems for regular trace languages, Math. Systems Theory, 22, 1-19 (1989) · Zbl 0679.68132
[2] Berstel, J.; Perrin, D., Theory of Codes, (Pure and Applied Mathematics, Vol. 117 (1985), Academic Press: Academic Press Orlando, FL) · Zbl 1022.94506
[3] Bertoni, A.; Mauri, G.; Sabadini, N., Equivalence and membership problems for regular trace languages, (Proc. 9th Internat. Colloq. on Automata, Languages and Programming (ICALP’82). Proc. 9th Internat. Colloq. on Automata, Languages and Programming (ICALP’82), Lecture Notes in Computer Science, Vol. 140 (1982), Springer: Springer Berlin), 61-71 · Zbl 0486.68079
[4] Bruyère, V.; De Felice, C.; Guaiana, G., Coding with traces, (Enjalbert, P.; Mayr, E.; Wagner, K. W., Proc. 11th Annual Symp. on Theoretical Aspects of Computer Science (STACS’94). Proc. 11th Annual Symp. on Theoretical Aspects of Computer Science (STACS’94), 1994. Proc. 11th Annual Symp. on Theoretical Aspects of Computer Science (STACS’94). Proc. 11th Annual Symp. on Theoretical Aspects of Computer Science (STACS’94), 1994, Lecture Notes in Computer Science, Vol. 775 (1994), Springer: Springer Berlin), 353-364 · Zbl 0941.68651
[5] 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
[6] Chrobak, M.; Rytter, W., Unique decipherability for partially commutative alphabets, Fund. Inform., X, 323-336 (1987) · Zbl 0634.94014
[7] Cori, R.; Perrin, D., Automates et commutations partielles, RAIRO Inform. Théor. Appl., 19, 21-32 (1985) · Zbl 0601.68055
[8] Diekert, V., Combinatorics on Traces, (Lecture Notes in Computer Science, Vol. 454 (1990), Springer: Springer Berlin) · Zbl 0717.68002
[9] Diekert, V.; Muscholl, A.; Reinhardt, K., On codings of traces, (Mayr, E.; Puech, C., Proc. 12th Annual Symp. on Theoretical Aspects of Computer Science (STACS’95). Proc. 12th Annual Symp. on Theoretical Aspects of Computer Science (STACS’95), 1995. Proc. 12th Annual Symp. on Theoretical Aspects of Computer Science (STACS’95). Proc. 12th Annual Symp. on Theoretical Aspects of Computer Science (STACS’95), 1995, Lecture Notes in Computer Science, Vol. 900 (1995), Springer: Springer Berlin), 385-396 · Zbl 1379.68243
[10] (Diekert, V.; Rozenberg, G., The Book of Traces (1995), World Scientific: World Scientific Singapore)
[11] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[12] Hotz, G.; Claus, V., (Automatentheorie und Formale Sprachen, Band III (1972), Bibliographisches Institut: Bibliographisches Institut Mannheim)
[13] Matyiasevich, Yu., (Cas décidables et indécidables du problème du codage our les monoïdes partialement commutatifs invited lecture delivered to Colloque National Recherches en I.U.T. en Mathematique (Feb. 14-16, 1996), Informatique et leur Applications: Informatique et leur Applications Clermont-Ferrand, France), to appear in Quadrature
[14] Mazurkiewicz, A., Concurrent program schemes and their interpretations, (DAIMI Rep. PB 78 (1977), Aarhus University: Aarhus University Aarhus)
[15] Ochmański, E., On morphisms of trace monoids, (Cori, R.; Wirsing, M., Proc. 5th Annual Symp. on Theoretical Aspects of Computer Science (STACS’88). Proc. 5th Annual Symp. on Theoretical Aspects of Computer Science (STACS’88), Lecture Notes in Computer Science, Vol. 294 (1988), Springer: Springer Berlin), 346-355
[16] Rytter, W., The space complexity of the unique decipherability problem, Inform. Process. Lett., 23, 1-3 (1986) · Zbl 0609.68037
[17] Sakarovitch, J., The ‘last’ decision problem for rational trace languages, (Simon, I., Proc. 1st Latin Amer. Symp. on Theoretical Informatics (LATIN’92). Proc. 1st Latin Amer. Symp. on Theoretical Informatics (LATIN’92), Lecture Notes in Computer Science, Vol. 583 (1992), Springer: Springer Berlin), 460-473
[18] Wagner, K.; Wechsung, G., Computational Complexity (1986), VEB Deutscher Verlag der Wissenschaften: VEB Deutscher Verlag der Wissenschaften Berlin · Zbl 0584.68061
[19] Wolk, E. S., A note on the comparability graph of a tree, (Proc. Amer. Math. Soc., 16 (1965)), 17-20 · Zbl 0137.18105
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.