Characterizations of the decidability of some problems for regular trace languages. (English) Zbl 0679.68132

Summary: The decidability of the equivalence problem and the disjointness problem for regular trace languages is considered. By describing the structure of the independence relations involved, precise characterizations are given of those concurrency alphabets for which these problems are decidable. In fact, the first problem is decidable if and only if the independence relation is transitive, while the second problem is decidable if and only if the independence relation is a so-called transitive forest.


68Q45 Formal languages and automata
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
Full Text: DOI


[1] Aalbersberg, IJ. J., and Engelfriet, J., The recognition of trace languages, Technical Report 86-18, University of Leiden, Leiden (1986).
[2] Aalbersberg, IJ. J., and Hoogeboom, H. J., Decidability problems for regular trace language,Proc. ICALP 87 (Th. Ottmann, ed.), Lecture Notes in Computer Science, Vol. 267, Springer-Verlag, Berlin (1987), pp. 250–259.
[3] Aalbersberg, IJ. J., and Rozenberg, G., Traces, dependency graphs and DNLC grammars,Discrete Appl. Math.,11 (1985), 299–306. · Zbl 0601.68045
[4] Aalbersberg, IJ. J., and Rozenberg, G., Theory of traces,Theoret. Comput. Sci.,60 (1988), 1–82. · Zbl 0652.68017
[5] Aalbersberg, IJ. J., and Welzl, E., Trace languages defined by regular string languages,RAIRO Inform. Théor.,20 (1986), 103–119. · Zbl 0612.68071
[6] Berstel, J.,Transductions and Context-Free Languages, Teubner, Stuttgart (1979). · Zbl 0424.68040
[7] Berstel, J., and Perrin, D.,Theory of Codes, Academic Press, New York (1985). · Zbl 0587.68066
[8] Bertoni, A., Brambilla, M., Mauri, G., and Sabadini, N., An application of the theory of free partially commutative monoids: asymptotic densities of trace languages,Proc. MFCS 81 (J. Gruska and M. Chytil, eds.), Lecture Notes in Computer Science, Vol. 118, Springer-Verlag, Berlin (1981), pp. 205–215. · Zbl 0468.68081
[9] Bertoni, A., Mauri, G., and Sabadini, N., Equivalence and membership problems for regular trace languages,Proc. ICALP 82 (M. Nielsen and E. M. Schmidt, eds.), Lecture Notes in Computer Science, Vol. 140, Springer-Verlag, Berlin (1982), pp. 61–71. · Zbl 0486.68079
[10] Bertoni, A., Mauri, G., and Sabadini, N., Unambiguous regular trace languages,Colloquia Mathematica Societas János Bolyai 42, North-Holland, Amsterdam (1985), pp. 113–123. · Zbl 0627.68060
[11] Berstel, J., and Sakarovitch, J., Recent results in the theory of rational sets,Proc. MFCS 86 (J. Gruska, B. Rovan, and J. Wiedermann, eds.), Lecture Notes in Computer Science, Vol. 233, Springer-Verlag, Berlin (1986), pp. 15–28. · Zbl 0618.68070
[12] Cartier, P., and Foata, D.,Problèmes combinatoires de commutations et réarrangements, Lecture Notes in Mathematics, Vol. 85, Springer-Verlag, Berlin (1969). · Zbl 0186.30101
[13] Choffrut, C., Free partially commutative monoids, Report 86-20, LITP, University of Paris 7, Paris (1986).
[14] Chrobak, M., and Rytter, W., Unique decipherability for partially commutative monoids,Fund. Inform.,X (1987), 323–336. · Zbl 0634.94014
[15] Clerbout, M., and Latteux, M., Partial commutations and faithful rational transductions,Theoret. Comput. Sci.,34 (1984), 241–254. · Zbl 0548.68073
[16] Cori, R., and Metivier, Y., Recognizable subsets of some partially abelian monoids,Theoret. Comput. Sci.,35 (1985), 179–189. · Zbl 0559.20040
[17] Cori, R., and Perrin, D., Automates et commutations partielles,RAIRO Inform. Théor.,19 (1985), 21–32. · Zbl 0601.68055
[18] Duboc, C., Commutations dans les monoides libres: un cadre théorique pour l’étude du parallélisme, Thesis, University of Rouen, Rouen (1986).
[19] Flé, M. P., and Roucairol, G., Fair serializability of iterated transactions using FIFO-nets,Advances in Petri Nets (G. Rozenberg, ed.), Lecture Notes in Computer Science, Vol. 188, Springer-Verlag, Berlin (1985), pp. 154–168. · Zbl 0562.68018
[20] Gibbons, A., and Rytter, W., On the decidability of some problems about rational subsets of free partially commutative monoids,Theoret. Comput. Sci.,48 (1986), 329–337. · Zbl 0638.68084
[21] Ginsburg, S.,The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York (1966). · Zbl 0184.28401
[22] Harary, F.,Graph Theory, Addison-Wesley, Reading, MA (1969).
[23] Harrison, M. A.,Introduction to Formal Language Theory, Addison-Wesley, Reading, MA (1978). · Zbl 0411.68058
[24] Hopcroft, J. E., and Ullman, J. D.,Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, MA (1979). · Zbl 0426.68001
[25] Ibarra, O. H., Reversal-bounded multicounter machines and their decision problems,J. Assoc. Comput. Mach.,25 (1978), 116–133. · Zbl 0365.68059
[26] Mazurkiewicz, A., Concurrent program schemes and their interpretations, DAIMI Report PB-78, Aarhus University, Arhus (1977).
[27] Mazurkiewicz, A., Traces, histories, graphs: instances of a process monoid,Proc. MFCS 84 (M. P. Chytil and V. Koubek, eds.), Lecture Notes in Computer Science, Vol. 176 Springer-Verlag, Berlin (1984), pp. 115–133. · Zbl 0577.68061
[28] Mazurkiewicz, A., Semantics of concurrent systems: a modular fixed-point trace approach,Advances in Petri Nets (G. Rozenberg, ed.), Lecture Notes in Computer Science, Vol. 188, Springer-Verlag, Berlin (1985), pp. 353–375.
[29] Métivier, Y., Une condition suffisante de reconnaissabilité dans un monoide partiellement commutatif,RAIRO Inform. Théor.,20 (1986), 121–127.
[30] Minsky, M. L., Recursive unsolvability of Post’s problem of ”tag” and other topics in theory of Turing Machines,Ann. of Math.,74 (1961), 437–455. · Zbl 0105.00802
[31] Minsky, M. L.,Computation: Finite and Infinite Machines, Prentice-Hall, London (1967). · Zbl 0195.02402
[32] Sardinas, A. A., and Patterson, C. W., A necessary and sufficient condition for the unique decomposition of coded messages,I.R.E. Internat. Conv. Rec.,8 (1953), 104–108.
[33] 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.