@article{GIBBONS1986329,
    Abstract = {Let I = A ∪ 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∗ × 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∪Y=0? (Q2): X⊆Y? (Q3): X=Y? (Q4): X=M? (Q5): M−X finite? (Q6): X is recognized? It is known (see (Berstel, 1979)) 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 (see (Choffrut, 1986, p. 79)) 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.},
    Author = {Gibbons, Alan and Rytter, Wojciech},
    File = {On the decidability of some problems about rational subsets of free partially commutative monoids - Gibbons, Rytter (0) (0) - a - a - x.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Pages = {329 - 337},
    Title = {On the decidability of some problems about rational subsets of free partially commutative monoids},
    URL = {http://www.sciencedirect.com/science/article/pii/0304397586901015},
    Volume = {48},
    Year = {1986},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/0304397586901015},
    bdsk-url-2 = {http://dx.doi.org/10.1016/0304-3975(86)90101-5},
    date-added = {2016-02-10 11:00:47 +0000},
    date-modified = {2016-02-10 11:00:47 +0000},
    doi = {10.1016/0304-3975(86)90101-5}
}

@article{GIBBONS1986329, Abstract = {Let I = A ∪ 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∗ × 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∪Y=0? (Q2): X⊆Y? (Q3): X=Y? (Q4): X=M? (Q5): M−X finite? (Q6): X is recognized? It is known (see (Berstel, 1979)) 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 (see (Choffrut, 1986, p. 79)) 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.}, Author = {Gibbons, Alan and Rytter, Wojciech}, File = {On the decidability of some problems about rational subsets of free partially commutative monoids - Gibbons, Rytter (0) (0) - a - a - x.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Pages = {329 - 337}, Title = {On the decidability of some problems about rational subsets of free partially commutative monoids}, URL = {http://www.sciencedirect.com/science/article/pii/0304397586901015}, Volume = {48}, Year = {1986}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/0304397586901015}, bdsk-url-2 = {http://dx.doi.org/10.1016/0304-3975(86)90101-5}, date-added = {2016-02-10 11:00:47 +0000}, date-modified = {2016-02-10 11:00:47 +0000}, doi = {10.1016/0304-3975(86)90101-5} }