I am writing an algorithm which is defined on two types that satisfy a relationship similar to a group action, but the "group" isn't really a group, and the "action" is a partial function.
But my actual problem is no fun to describe, so...
Let's stick a pip in a maze instead:
This is a charicature; the location of the pip represents the current state of my computation. The walls represent barriers to computation; they're bad news and we want nothing to do with them!
Our goal in this maze is immaterial. For now, we're just moving the pip around. In reality, the current position of the pip is not merely $\text{C5}$ but rather «several hundred MB of data». The purpose of all of the operations defined below is that they enable the algorithm at any given time to compute the next position it desires by destructively transforming its current position.
Define two sets:
Let $X\equiv\{ABCDE\}\times\{123456789\}$ be the set of maze positions.
Let $G$ be the set of maze navigation operations, defined as sequences of motions along orthogonal directions (Up, Left, Down, Right):
- '' or $\varepsilon$ is the identity operation.
- 'LLD' is motion two squares left, followed one down.
- For reasons soon to be made clear, $\text{'LR'} \ne \varepsilon$, $\text{'LLD'} \ne \text{'LDL'}$, and etc.
Define three operations:
First, a combining operator $~\& : G \times G \to G$ which concatenates the strings.
Next, an inversion-like operation $~\overline{◌}: G \to G$ which reverses the string and flips each direction. e.g. $\overline{\text{"LLDL"}} = \text{"RURR"}$.
Finally, an application operator $~* : X \times G \to X$, which moves the pip along the given path. Unfortunately, $*$ is a partial function, because the walls are super evil:
- $\text{C5}*\text{'R'}$ is defined and is equal to $\text{C6}$.
- $\text{C5}*\text{'L'}$ is not defined because it passes the pip through a wall.
- $\text{C5}*\text{'LR'}$ is likewise not defined, but $\text{C5}*\text{'RL'}=\text{C5}.$
Now what do we have?
I imagine it would be mathematical heresy to call $(G,X,\&,*)$ a group action, because $(G,\&)$ is not a group (it is a monoid), and $*$ is not total!
Nonetheless, it has several properties that suspiciously resemble a group action:
- Identity: $~~x * \varepsilon = x.~$ Period.
- Compatibility-ish property w.r.t. the combining operator:
- If $x * g$ and $(x * g) * h$ both exist, then $x * (g\,\&\,h)$ exists and equals $(x * g) * h$.
- Compatibility-ish property w.r.t. treating the inverse-like-things as inverses:
- If $x * g$ exists, then $(x * g) * \overline{g}$ exists and equals $x$.
These are the properties required by my algorithm.
The question:
I gotta document this thing somehow, and not with an image of a pip in a maze. What on earth do I call this structure? Is it well understood? Are there papers I can cite? Or have I somehow wandered into some no-man's land with my bizarre formulation?
This is most likely homotopy theory. You have (continuous) paths on a two-cell complex with non-trivial topology (basically your maze is the two complex with quad cells, the walls and the solid vertices are edges and vertices removed from the complex, so its topology is non-trivial) and when you go from one square (say C5) to another (say A#) along two different paths (say $C5,B5,B4,B3,A3$ and say $C5,C6,C5,B5,B4,B3,B2,B1,B2,B3,A3$) that are not separated by any obstructions, then you can "homotope" one path into the other. Going around in loops then gives rise to the fundamental group of the cell complex, which in this case is a free group because the complex deformation retracts onto a one-complex (a graph). I suggest you look into cell complexes, fundamental groups and homotopy theory. Just Wiki it at first to get an idea.
Edit. In this line of thought, check out Cayley graphs. Just Wiki it and you will see the graph (one dimensional cell complex) related to a finitely generated group (more like finitely generated, finitely presented group). You assign an element of the group to each vertex of the graph and you connect two vertices by an edge if you can get from one element to another by applying a generator of the group. If there are (identity) relations, like the product of some elements being identity, then it corresponds to a closed cycle in the Calyey graph. You can even attach faces (two dimensional cells, i.e. topological discs) to each relation, obtaining a two dimensional complex. If your group is a free group (only generators, no relations) you end up with a graph that is a regular tree. A group given by generators and relations is universally covered by a free group. In general, when you have a space with complicated topology, sometimes moveing around that space can be done through unfolding the space into the so called universal covering space (Wiki that too after the Cayley graphs) which has trivial, elementary topology, but you keep the information of the underlying folded complicated space into a group of deck symmetries acting on the universal covering space. I have used these technique on one or two occasions in the development of algorithms.