On the decidability of some problems about rational subsets of free partially commutative monoids
DOI10.1016/0304-3975(86)90101-5zbMATH Open0638.68084OpenAlexW2035413543MaRDI QIDQ1099641FDOQ1099641
Authors: Wojciech Rytter, A. Gibbons 
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/60778/12/WRAP_cs-rr-079.pdf
Recommendations
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)
Cites Work
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (22)
- Some decidable congruences of free monoids
- Identities and transductions
- Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable
- Rational, recognizable, and aperiodic sets in the partially lossy queue monoid
- The equality problem for rational series with multiplicities in the tropical semiring is undecidable
- On the complexity of reasoning in Kleene algebra with commutativity conditions
- Characterizations of the decidability of some problems for regular trace languages
- On recognizable subsets of free partially commutative monoids
- On the complexity of reasoning in Kleene algebra
- Title not available (Why is that?)
- On lindenmayerian rational subsets of monoids
- Decision problems among the main subfamilies of rational relations
- Recognizable closures and submonoids of free partially commutative monoids
- Probabilistic estimation of the number of prefixes of a trace
- On the rational subsets of the monogenic free inverse monoid
- String matching problems over free partially commutative monoids
- On the decidability of the equivalence problem for partially commutative rational power series
- Rational relations and rational series
- Rational subsets of partially reversible monoids
- Title not available (Why is that?)
- Limitedness theorem on finite automata with distance functions: An algebraic proof
- Rational, recognizable, and aperiodic partially lossy queue languages
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)
