On the decidability of some problems about rational subsets of free partially commutative monoids

DOI10.1016/0304-3975(86)90101-5MaRDI QIDQ1099641zbMATHOpenAlexFDO

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

zbMATH Keywords

regular expressionsfree partially commutative monoidrational subsetsdecidabilty

Mathematics Subject Classification ID

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)

Recommendations

• Recognizable subsets of some partially Abelian monoids
• A decision procedure on partially commutative free monoids
• Rational subsets of partially reversible monoids
• scientific article; zbMATH DE number 3956459
• On recognizable subsets of free partially commutative monoids

Cites work

• 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

Cited in

(22)

• On recognizable subsets of free partially commutative monoids
• On the decidability of the equivalence problem for partially commutative rational power series
• Rational relations and rational series
• The equality problem for rational series with multiplicities in the tropical semiring is undecidable
• Rational subsets of partially reversible monoids
• On the complexity of reasoning in Kleene algebra
• On the complexity of reasoning in Kleene algebra with commutativity conditions
• Identities and transductions
• Probabilistic estimation of the number of prefixes of a trace
• On lindenmayerian rational subsets of monoids
• String matching problems over free partially commutative monoids
• Decision problems among the main subfamilies of rational relations
• Characterizations of the decidability of some problems for regular trace languages
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• Rational, recognizable, and aperiodic sets in the partially lossy queue monoid
• On the rational subsets of the monogenic free inverse monoid
• Recognizable closures and submonoids of free partially commutative monoids
• Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable
• scientific article; zbMATH DE number 4003548 (Why is no real title available?)
• Rational, recognizable, and aperiodic partially lossy queue languages
• scientific article; zbMATH DE number 4033664 (Why is no real title available?)
• Some decidable congruences of free monoids

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)