Detecting plainness in PSPACE

Murray Elder, Adam Piggott

We show that groups presented by inverse-closed finite convergent length-reducing rewriting systems are characterised by a striking geometric property: non-degenerate triangles in their Cayley graph have uniformly bounded size. We then define a simple relation on the set of non-trivial finite-order elements of the group, and prove that the group is plain if and only if this relation is transitive on a bounded set. This in turn gives rise to a deterministic quadratic space algorithm (in the size of the longest right-hand side of a rule in the rewriting system) to decide whether or not the group is plain.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment