On the decidability of some problems about rational subsets of free partially commutative monoids. (English) Zbl 0638.68084

Let \(I=A\cup B\) be a partially commutative alphabet such that two letters commute iff one of them belongs to A and the other one belongs to B. Let \(M=A^*\times B^*\) denote the free partially commutative monoid generated by I. We consider the following six problems for rational (given by regular expressions) subsets \(X,Y\) of \(M\): \[ (Q1): X\cap Y=\emptyset? \quad (Q2): X\subseteq Y? \quad (Q3): X=Y? \quad (Q4): X=M? \quad (Q5): M-X \text{ finite?} \quad (Q6): X\text{ is recognizable?} \] It is known [see J. Berstel, Transductions and context-free languages (1979; Zbl 0424.68049)] that all these problems are undecidable if Card\(A>1\) and Card\(B>1\), and they are decidable if Card\(A=\) Card\(B=1\) (Card\(U\) denotes the cardinality of U).
It was conjectured by C. Choffrut that these problems are decidable in the remaining cases, where Card\(A=1\) and Card\(B>1\). In this paper we show that if Card\(A=1\) and Card\(B>1\), then the problem (Q1) is decidable,and problems (Q2)-(Q6) are undecidable. Our paper is an application of results concerning reversal-bounded, nondeterministic, multicounter machines and nondeterministic, general sequential machines.


68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
03D05 Automata and formal grammars in connection with logical questions
Full Text: DOI Link


[1] Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040
[2] Bertoni, A.; Mauri, G.; Sabadini, N., Equivalence and membership problem for regular trace languages, (), 61-71 · Zbl 0486.68079
[3] Choffrut, C., Free partially commutative monoids, Tech. rept. laboratoire informatique théorique et programmation 86.20, (March 1986)
[4] Chrobak, M.; Rytter, W., The unique decipherability problem with partially commutative alphabet, (), 256-263
[5] Ibarra, O.H., Reversal-bounded multicounter machines and their decision problems, J. ACM, 25, 1, 106-133, (1978) · Zbl 0365.68059
[6] Ibarra, O.H., The unsolvability of the equivalence problem for e-free Ngsm’s with unary input (output) alphabet and applications, SIAM J. comput., 7, 4, 524-532, (1978) · Zbl 0386.68054
[7] Mazurkiewicz, A., Concurrent program schemes and their interpretations, ()
[8] Mazurkiewicz, A., Traces, histories, graphs: instances of processes monoid, (), 115-133
[9] Rytter, W., Some properties of trace languages, Fund. inform., VII, 1, 107-127, (1984) · Zbl 0546.68064
[10] Szijarto, M., A classification and closure properties of languages for describing concurrent systems behaviours, Fund. inform., IV, 3, 531-550, (1981) · Zbl 0486.68074
[11] Tarlecki, A., Notes on the implementability of formal languages by concurrent systems, ICS PAS repts. 481, (1982), Warsaw
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.