Rewriting systems for finitely presented groups.

miguelmarco commented 10 years ago

This patch adds a class for rewriting systems for finitely presented groups. Rewriting systems can be used (when the Knuth-Bendix algorithms finishes in finite time) to get reduced forms of the elements of the group, the same way that groebner basis can be used to get normal forms of elements of polynomial rings modulo ideals.

This class is just a wrapper of corresponding GAP functions.

Examples:

sage: F.<a,b> = FreeGroup()
sage: G=F / [a*b/a/b]
sage: k = G.rewriting_system()
sage: k
Knuth Bendix Rewriting System for Monoid( [ a, A, b, B ], ... ) with
rules
[ [ a*A, <identity ...> ], [ A*a, <identity ...> ], [ b*B,
<identity ...> ], [ B*b, <identity ...> ], [ a*b*A*B,
<identity ...> ] ]
sage: k.reduce(a*b*a*b)
(a*b)^2
sage: k.make_confluent()
sage: k
Knuth Bendix Rewriting System for Monoid( [ a, A, b, B ], ... ) with
rules
[ [ a*A, <identity ...> ], [ A*a, <identity ...> ], [ b*B,
<identity ...> ], [ B*b, <identity ...> ], [ B*A, A*B ], [
b*A, A*b ], [ B*a, a*B ], [ b*a, a*b ] ]
sage: k.reduce(a*b*a*b)
a^2*b^2

CC: @vbraun @tscrim @dimpase

Component: group theory

Keywords: finitely presented groups

Author: Miguel Angel Marco Buzunariz

Branch/Commit: u/mmarco/ticket/15528 @ 810a9bb

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/15528

miguelmarco commented 10 years ago

comment:1

Attachment: 15528_rewriting_systems.patch.gz

miguelmarco commented 10 years ago

Branch: u/mmarco/ticket/15528

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Commit: fbcb3a3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

fbcb3a3 Added rewriting systems of finitely presented groups

tscrim commented 10 years ago

Reviewer: Travis Scrimshaw

tscrim commented 10 years ago

Changed branch from u/mmarco/ticket/15528 to u/tscrim/ticket/15528

tscrim commented 10 years ago

Changed author from mmarco to Miguel Angel Marco Buzunariz

tscrim commented 10 years ago

Changed commit from fbcb3a3 to ed1095d

tscrim commented 10 years ago

comment:5

I've made some review changes, so if you agree with them, then you can set this to positive review.

Best,

Travis

New commits:

`6268cca`	`Merge branch 'u/mmarco/ticket/15528' of trac.sagemath.org:sage into u/tscrim/ticket/15528`
`504df8f`	`Merge branch 'develop' of trac.sagemath.org:sage into u/tscrim/ticket/15528`
`cfbb6e5`	`Review changes for #15528.`
`ed1095d`	`Made the repr sorted for the rules.`

miguelmarco commented 10 years ago

comment:6

Looks good to me. Maybe i should add some methods to return the fpgroup and the free group that it relates to. But i don't know if it would be better in another ticket or is it good to add it here.

tscrim commented 10 years ago

comment:7

I think it's fine (maybe even good) to do so here.

miguelmarco commented 10 years ago

Changed branch from u/tscrim/ticket/15528 to u/mmarco/ticket/15528

miguelmarco commented 10 years ago

comment:9

Added the two methods .free_group() and .finitely_presented_group()

tscrim commented 10 years ago

comment:10

I don't see the changes.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from ed1095d to 810a9bb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

810a9bb Added free_group and finitely_presented_group

miguelmarco commented 10 years ago

comment:12

sorry, i forgot to commit. There they are.

tscrim commented 10 years ago

comment:13

No worries. Looks good.

sagemath / sage

Rewriting systems for finitely presented groups. #15528