On two problems related to cancellativity
From MaRDI portal
Publication:1070349
DOI10.1007/BF02573208zbMath0584.20046MaRDI QIDQ1070349
Publication date: 1986
Published in: Semigroup Forum (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/134818
decision problemsfinite presentationsfinite Church-Rosser Thue systemsleft-cancellativityright-cancellativity
Related Items
Restrictions of congruences generated by finite canonical string-rewriting systems ⋮ Some independence results for equational unification ⋮ Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems ⋮ Equational unification, word unification, and 2nd-order equational unification ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ On ground-confluence of term rewriting systems ⋮ When is an extension of a specification consistent? Decidable and undecidable cases ⋮ Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Decidable sentences of Church-Rosser congruences
- Conjugacy in monoids with a special Church-Rosser presentation is decidable
- Some undecidability results for non-monadic Church-Rosser Thue systems
- Complexity results on the conjugacy problem for monoids
- On deciding whether a monoid is a free monoid or is a group
- The problems of cyclic equality and conjugacy for finite complete rewriting systems
- Thue congruences and the Church-Rosser property
- Cancellativity in finitely presented semigroups
- Relationships between nondeterministic and deterministic tape complexities
- Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems
- The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
- Church–Rosser Thue Systems that Present Free Monoids
- Confluent and Other Types of Thue Systems
