Conjugacy in monoids with a special Church-Rosser presentation is decidable

conjugacy problem decidability word problem free monoids equivalence relations finitely presented monoids Church-Rosser Thue systems conjugacy relations

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Mappings of semigroups (20M15)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Recursive Unsolvability of a problem of Thue
Confluent and Other Types of Thue Systems
Monadic Thue systems
Decidable sentences of Church-Rosser congruences
Recursively enumerable degress and the conjugacy problem
On monoids presented by a single relation

Cited In (33)

On equations and first-order theory of one-relator monoids
A note on regular classes in special Thue systems
Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids
On two problems related to cancellativity
Thue systems as rewriting systems
Decision problems for finite special string-rewriting systems that are confluent on some congruence class
The transitivity of primary conjugacy in regular \(\omega\)-semigroups
Conjugacy in inverse semigroups
The monoid of queue actions
Deciding conjugacy in sylvester monoids and other homogeneous monoids
Efficient solution of some problems in free partially commutative monoids
Commutativity in groups presented by finite Church-Rosser Thue systems
The Knuth-Bendix algorithm and the conjugacy problem in monoids.
Conjugation in semigroups.
Normal subsemigroups of finite transformation semigroups
Generalized notion of conjugacy in semigroups
Finite derivation type for Rees matrix semigroups
On Finite Complete Presentations and Exact Decompositions of Semigroups
The word problem for one-relation monoids: a survey
Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems
Idempotent varieties of incidence monoids and bipartite posets
Complexity results on the conjugacy problem for monoids
The problems of cyclic equality and conjugacy for finite complete rewriting systems
Conjugacy in special monoids
On three approaches to conjugacy in semigroups.
Combinatorics of cyclic shifts in plactic, hypoplactic, Sylvester, Baxter, and related monoids
A new definition of conjugacy for semigroups
Decidability and independence of conjugacy problems in finitely presented monoids
Crystallizing the hypoplactic monoid: from quasi-Kashiwara operators to the Robinson-Schensted-Knuth-type correspondence for quasi-ribbon tableaux
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Semigroups presented by one relation and satisfying the Church-Rosser property

This page was built for publication: Conjugacy in monoids with a special Church-Rosser presentation is decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q801163)