The Setting
The head of a two-way automaton crosses a block of tape cells along paths that enter through one end of the block and leave through one end, possibly the same one. A boundary diagram on labels records such crossings, with labels for each direction of travel. Gluing two blocks side by side multiplies their diagrams, and a path through the glued block may pass back and forth between the two parts any number of times before it leaves.
The item compares these diagrams with the monoid of binary relations on a finite set of points, under the path-order product, in which when and for some , and with identity .
Diagrams and the Loss Bound
A boundary diagram on labels is a quadruple of relations on two copies and of an -element label set: the forward relation , the backward relation , the left relation and the right relation .β¦ The pairs in these relations are the edges of , its crossings: an edge of enters on the left and exits on the right, one of enters on the right and exits on the left, one of enters and exits on the left, and one of enters and exits on the right. The set of boundary diagrams on labels is .
The reflexive transitive closure of a relation on a set is the relation on , where and .β¦
The product of diagrams and in , which glues to the left of , is the diagram in with relations, composed in path order, (1)β¦
The identity diagram is the diagram in with forward relation , backward relation and empty left and right relations.β¦
Edge inclusion is the relation on under which when each of the four relations of is contained in the corresponding relation of .β¦
The loss bound of a natural number is (2)β¦
The Claim
Theorem 1. Let , and let be a finite set with . Let be a set of diagrams in that contains and is closed under the product, and let be a surjective map with for all and with whenever and . Then (3)β¦ In particular, when for some , (4)β¦
In the paper, the result reads: if , is a finite set with , is a submonoid of and a surjective multiplicative map , which need not preserve identities, satisfies whenever , then .
What Is Checked
The claims (3) and (4) are stated over boundary diagrams on labels, their product (1) with the reflexive transitive closure in it, the identity diagram , edge inclusion , the monoid of relations on a finite set, and the loss bound (2).