Repository logo
 

Undecidability and the developability of permutoids and rigid pseudogroups

Published version
Peer-reviewed

Change log

Authors

Bridson, MR 
Wilton, HJR 

Abstract

A permutoid is a set of partial permutations that contains the identity and is such that partial compositions, when defined, have at most one extension in the set. In 2004 Peter Cameron conjectured that there can exist no algorithm that determines whether or not a permutoid based on a finite set can be completed to a finite permutation group. In this note we prove Cameron’s conjecture by relating it to our recent work on the profinite triviality problem for finitely presented groups. We also prove that the existence problem for finite developments of rigid pseudogroups is unsolvable. In an appendix, Steinberg recasts these results in terms of inverse semigroups.

Description

Keywords

math.GR, math.GR, math.CO, math.LO, 20F10, 05C60, (20M18, 08A50)

Journal Title

Forum of Mathematics, Sigma

Conference Name

Journal ISSN

2050-5094
2050-5094

Volume Title

5

Publisher

Cambridge University Press
Sponsorship
Bridson and Wilton thank the EPSRC for its financial support. Bridson’s work is also supported by a Wolfson Research Merit Award from the Royal Society.