On the decidability of some problems about rational subsets of free partially commutative monoids (Q1099641)

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 \textit{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 \textit{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.