Complexity results on the conjugacy problem for monoids
From MaRDI portal
(Redirected from Publication:1073015)
Thue and Post systems, etc. (03D03) Complexity of computation (including implicit computational complexity) (03D15) Free semigroups, generators and relations, word problems (20M05) Other degrees and reducibilities in computability and recursion theory (03D30) Word problems, etc. in computability and recursion theory (03D40)
Recommendations
- Complexity of the generalized conjugacy problem
- The Knuth-Bendix algorithm and the conjugacy problem in monoids.
- Decidability and independence of conjugacy problems in finitely presented monoids
- Computational complexity and the conjugacy problem
- Computations over finite monoids and their test complexity
- Complexity issues of checking identities in finite monoids
- scientific article; zbMATH DE number 1303030
- scientific article; zbMATH DE number 1504638
- Generic complexity of finitely presented monoids and semigroups
- Computational complexity of some problems involving congruences on algebras
Cites work
- scientific article; zbMATH DE number 3811849 (Why is no real title available?)
- scientific article; zbMATH DE number 3654376 (Why is no real title available?)
- scientific article; zbMATH DE number 3711944 (Why is no real title available?)
- scientific article; zbMATH DE number 3756462 (Why is no real title available?)
- scientific article; zbMATH DE number 3482316 (Why is no real title available?)
- scientific article; zbMATH DE number 3563392 (Why is no real title available?)
- scientific article; zbMATH DE number 3634526 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- scientific article; zbMATH DE number 3083488 (Why is no real title available?)
- scientific article; zbMATH DE number 3090995 (Why is no real title available?)
- Confluent and Other Types of Thue Systems
- Conjugacy in monoids with a special Church-Rosser presentation is decidable
- Decidable sentences of Church-Rosser congruences
- Infinite regular Thue systems
- Monadic Thue systems
- On the computational power of pushdown automata
- Recursive unsolvability of a problem of Thue
- Recursively enumerable degress and the conjugacy problem
- Relationships between nondeterministic and deterministic tape complexities
- The Church-Rosser property and special Thue systems
- The equation \(a_ M=b^ Nc^ P\) in a free group
Cited in
(19)- Incidence monoids: automorphisms and complexity
- On equations and first-order theory of one-relator 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 COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS
- scientific article; zbMATH DE number 4216027 (Why is no real title available?)
- scientific article; zbMATH DE number 88945 (Why is no real title available?)
- The Knuth-Bendix algorithm and the conjugacy problem in monoids.
- On deciding whether a monoid is a free monoid or is a group
- scientific article; zbMATH DE number 7444014 (Why is no real title available?)
- STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
- scientific article; zbMATH DE number 1418332 (Why is no real title available?)
- About the descriptive power of certain classes of finite string-rewriting systems
- Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems
- The problems of cyclic equality and conjugacy for finite complete rewriting systems
- Decidability and independence of conjugacy problems in finitely presented monoids
- Deciding conjugacy in Sylvester monoids and other homogeneous monoids.
- Conjugacy in monoids with a special Church-Rosser presentation is decidable
This page was built for publication: Complexity results on the conjugacy problem for monoids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1073015)
