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

Gibbons, Alan; Rytter, Wojciech

Theor. Comput. Sci. 48, 329-337 (1986).

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.

MSC:

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

Keywords:

decidabilty; rational subsets; free partially commutative monoid; regular expressions

Citations:

Zbl 0491.68053; Zbl 0424.68049

References:

[1]	Berstel, J., Transductions and Context-free Languages (1979), Teubner: Teubner Stuttgart · Zbl 0424.68040
[2]	Bertoni, A.; Mauri, G.; Sabadini, N., Equivalence and membership problem for regular trace languages, (ICALP ’82. ICALP ’82, Lecture Notes in Computer Science, 140 (1982), Springer: Springer Berlin), 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, (Proc. Math. Found. of Comput. Science. Proc. Math. Found. of Comput. Science, Lecture Notes in Computer Science, 233 (1986), Springer: Springer Berlin), 256-263 · Zbl 0618.68063
[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, (DAIMIPB 78 (1977), Aarhus University)
[8]	Mazurkiewicz, A., Traces, histories, graphs: instances of processes monoid, (Lecture Notes in Computer Science, 176 (1984), Springer: Springer Berlin), 115-133 · Zbl 0577.68061
[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