On the decidability of some problems about rational subsets of free partially commutative monoids
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.
- scientific article; zbMATH DE number 3870628 (Why is no real title available?)
- scientific article; zbMATH DE number 3924146 (Why is no real title available?)
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 3765174 (Why is no real title available?)
- scientific article; zbMATH DE number 3765179 (Why is no real title available?)
- scientific article; zbMATH DE number 4003548 (Why is no real title available?)
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- The Unsolvability of the Equivalence Problem for \varepsilon -Free NGSM’s with Unary Input (Output) Alphabet and Applications
- On recognizable subsets of free partially commutative monoids
- Recognizable closures and submonoids of free partially commutative monoids
- Probabilistic estimation of the number of prefixes of a trace
- On the decidability of the equivalence problem for partially commutative rational power series
- Rational relations and rational series
- String matching problems over free partially commutative monoids
- Rational subsets of partially reversible monoids
- On the complexity of reasoning in Kleene algebra
- On the rational subsets of the monogenic free inverse monoid
- Rational, recognizable, and aperiodic sets in the partially lossy queue monoid
- Decision problems among the main subfamilies of rational relations
- scientific article; zbMATH DE number 4033664 (Why is no real title available?)
- On lindenmayerian rational subsets of monoids
- The intersection problem for alphabetic vector monoids
- scientific article; zbMATH DE number 4003548 (Why is no real title available?)
- Characterizations of the decidability of some problems for regular trace languages
- Some decidable congruences of free monoids
- Rational, recognizable, and aperiodic partially lossy queue languages
- The equality problem for rational series with multiplicities in the tropical semiring is undecidable
- Identities and transductions
- On the complexity of reasoning in Kleene algebra with commutativity conditions
- Kleene algebra with commutativity conditions is undecidable
- Limitedness theorem on finite automata with distance functions: An algebraic proof
- Separability of rational relations in A^* N^m by recognizable relations is decidable
This page was built for publication: On the decidability of some problems about rational subsets of free partially commutative monoids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099641)
