The Library
On the decidability of some problems about rational subsets of free partially commutative monoids
Tools
Tools
Tools
Gibbons, Alan (Alan M.) and Rytter, Wojciech (1986) On the decidability of some problems about rational subsets of free partially commutative monoids. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-079.pdf - Requires a PDF viewer. Download (6Mb) | Preview |
Abstract
Let I=A+B be a partially commutative alphabet such that two letters commute if 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= O?
Q2: X ⊆ Y?
DI X = Y?
Q4: X = M?
L25: M — X finite?
X is recognizable?
It was proved by Choffrut (see [2]) 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 [2], 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 01 is decidable, and problems Q2-06 are undecidable. Our paper is an application of results concerning reversal-bounded nondeterministic multicounter machines and nondeterministic general sequential machines.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Machine theory, Monoids | ||||
| Series Name: | Department of Computer Science Research Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Place of Publication: | Coventry, UK | ||||
| Official Date: | August 1986 | ||||
| Dates: |
|
||||
| Number: | Number 79 | ||||
| Number of Pages: | 8 | ||||
| DOI: | CS-RR-079 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | A.M. Gibbons and W. Rytter, “On the Decidability of some Problems about Rational Subsets of Free Partially Commutative Monoids”, <i>Theoretical Computer Science</i> <b>48</b>, pp. 329-337 (1986) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
