Formula reduction for Polyominoes
Contents:
# Introduction
In the last blog, I discussed about some fundamental rules for the shape algebra. I closed with a remark on how we’re able to not construct shapes like these:
In this blog, I’ll explore a way of solving this first, then I’ll write some generalized notation so that we can talk about the length of the formula as a “feature” of the algebra and ponder over it.
# Introducing Subtraction
The rules are the exact same as adding a block, except that when we write $-1_C$ we’ll be removing the first block it hits. All other rules stay the same. With this in place, I had to use all the existing rules to carve out the shape above, and here’s how it looks like:
# WRITE THIS IN OLD FORM
$$ A_R^3(1_C)C(1_C)M_C1_CCP1_CC1_C(1_C\cdot3)M_C(-1_R)P(-1_R)C(1_R)C(1_R) $$
Explanation:
# Notation and reduction
You would have realized that there are a lot of unncessary brackets and plus signs. I mean addition is understood, so we can get rid of those and assume addition by default. We can also get rid of the brackets because its one block at a time always going to the right.
So, a formula can be written in a simplified manner:
$$ OLD FORM \implies A_R^3(1_C)C(1_C)M_C1_CCP1_CC1_C(1_C\cdot3)M_C(-1_R)P(-1_R)C1_RC1_R $$
This is a great relief tbh. Now let’s talk about some reduction formulas:
$$ M_{X}M_{X} = \text{empty} $$
$$ A_X^{j+k} = A_X^j(1_X \cdot k) \forall j,k \in N $$
$$ M_{X}M_{Y} = M_{Y}M_{X} \forall X \neq Y $$
So with these, we can reduce an obviously wrong formula into the simplest form:
$$ A_C^{2}1_C1_{R}M_{R}M_{C}M_{C}M_{R} \to A_C^{3}1_R $$
There are a few more:
$$ A_X^{j}(1_Y \cdot (j-1))M_Y = A_Y^{j}(1_X \cdot (j-1))M_X $$
In fact it is this obeservation that led me to adding subtraction in the rules and discovering the new formula for the unspeakable shape.
# Coverage
I ran some scripts.