Cancellativity in finitely presented semigroups

DOI10.1016/S0747-7171(89)80028-8zbMath0682.20046OpenAlexW4210679658MaRDI QIDQ1824041

Paliath Narendran, Colm P. O'Dunlaing

Publication date: 1989

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0747-7171(89)80028-8

zbMATH Keywords

finitely presented semigroupsChurch-Rosser Thue systemscancellativityundecidablecommutative Thue systemssemigroups presented by Thue systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)

Related Items (8)

Restrictions of congruences generated by finite canonical string-rewriting systems ⋮ On deciding the confluence of a finite string-rewriting system on a given congruence class ⋮ Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ Commutativity in groups presented by finite Church-Rosser Thue systems ⋮ When is an extension of a specification consistent? Decidable and undecidable cases ⋮ A deterministic algorithm to decide if a finitely presented abelian monoid is cancellative ⋮ On two problems related to cancellativity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decidable sentences of Church-Rosser congruences
• Complexity of certain decision problems about congruential languages
• Thue systems as rewriting systems
• New decision algorithms for finitely presented commutative semigroups
• Testing for the Church-Rosser property
• Undecidable questions related to Church-Rosser Thue systems
• The Knuth-Bendix Completion Procedure and Thue Systems
• Confluent and Other Types of Thue Systems
• Elementary properties of Abelian groups

This page was built for publication: Cancellativity in finitely presented semigroups