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

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

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

decidabiltyfree partially commutative monoidrational subsetsregular expressions

Mathematics Subject Classification ID

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) Formal languages and automata (68Q45)

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

(24)

• 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)