TY - GEN
T1 - Geodesic rewriting systems and pregroups
AU - Diekert, Volker
AU - Duncan, Andrew J.
AU - Myasnikov, Alexei G.
N1 - Publisher Copyright:
© 2010 Springer Basel AG.
PY - 2010
Y1 - 2010
N2 - In this paper we study rewriting systems for groups and monoids, focusing on situations where finite convergent systems may be difficult to find or do not exist. We consider systems which have no length increasing rules and are confluent and then systems in which the length reducing rules lead to geodesics. Combining these properties we arrive at our main object of study which we call geodesically perfect rewriting systems. We show that these are well behaved and convenient to use, and give several examples of classes of groups for which they can be constructed from natural presentations. We describe a Knuth-Bendix completion process to construct such systems, show how they may be found with the help of Stallings' pregroups and conversely may be used to construct such pregroups.
AB - In this paper we study rewriting systems for groups and monoids, focusing on situations where finite convergent systems may be difficult to find or do not exist. We consider systems which have no length increasing rules and are confluent and then systems in which the length reducing rules lead to geodesics. Combining these properties we arrive at our main object of study which we call geodesically perfect rewriting systems. We show that these are well behaved and convenient to use, and give several examples of classes of groups for which they can be constructed from natural presentations. We describe a Knuth-Bendix completion process to construct such systems, show how they may be found with the help of Stallings' pregroups and conversely may be used to construct such pregroups.
KW - Geodesically Perfect
KW - Knuth-Bendix
KW - Stallings pregroups
KW - String rewriting systems
UR - http://www.scopus.com/inward/record.url?scp=84975730920&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84975730920&partnerID=8YFLogxK
U2 - 10.1007/978-3-7643-9911-5_3
DO - 10.1007/978-3-7643-9911-5_3
M3 - Conference contribution
AN - SCOPUS:84975730920
SN - 9783764399108
T3 - Trends in Mathematics
SP - 55
EP - 91
BT - Combinatorial and Geometric Group Theory
A2 - Bogopolski, Oleg
A2 - Bumagin, Inna
A2 - Kharlampovich, Olga
A2 - Ventura, Enric
T2 - International Conference on Combinatorial and Geometric Group Theory with Applications, GAGTA 2007
Y2 - 27 August 2007 through 31 August 2007
ER -