Finite derivation type for Rees matrix semigroups

DOI10.1016/j.tcs.2005.12.011zbMath1088.68082OpenAlexW1985270805MaRDI QIDQ2368998

António Malheiro

Publication date: 28 April 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.12.011

zbMATH Keywords

PresentationSemigroupFinite derivation type

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Grammars and rewriting systems (68Q42)

Related Items

Finite derivation type for large ideals. ⋮ Homotopy bases and finite derivation type for subgroups of monoids. ⋮ Finite derivation type for semilattices of semigroups. ⋮ Homological finiteness properties of monoids, their ideals and maximal subgroups. ⋮ On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids ⋮ On Finite Complete Presentations and Exact Decompositions of Semigroups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• A note on a special one-rule semi-Thue system
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Finite derivation type for semi-direct products of monoids
• Finite complete rewriting systems and finite derivation type for small extensions of monoids
• A finiteness condition for rewriting systems
• Finite derivation type implies the homological finiteness condition \(FP_ 3\)
• A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
• Structure Results for Transitive, Untwisted, Superlinked Finite Covers
• Generators and relations of Rees matrix semigroups
• THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS
• SECOND ORDER DEHN FUNCTIONS OF GROUPS AND MONOIDS
• LOW-DIMENSIONAL HOMOTOPY THEORY FOR MONOIDS