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

DOI10.1016/0304-3975(86)90101-5zbMath0638.68084OpenAlexW2035413543MaRDI QIDQ1099641

Wojciech Rytter, Alan M. 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 expressionsrational subsetsfree partially commutative monoiddecidabilty

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Automata and formal grammars in connection with logical questions (03D05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Unnamed Item, Rational, recognizable, and aperiodic partially lossy queue languages, Identities and transductions, Recognizable closures and submonoids of free partially commutative monoids, Probabilistic estimation of the number of prefixes of a trace, Rational relations and rational series, String matching problems over free partially commutative monoids, On the complexity of reasoning in Kleene algebra, The equality problem for rational series with multiplicities in the tropical semiring is undecidable, Characterizations of the decidability of some problems for regular trace languages, Limitedness theorem on finite automata with distance functions: An algebraic proof

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item