The Setting
A two-way automaton running on a word may visit a factor of the word many times, entering across either of the factor’s two boundaries and leaving across either. Its behaviour on the factor relates entries to exits, and the behaviour on a concatenation comes from the behaviours on and on : a visit to may cross the boundary between and back and forth any number of times before it leaves.
Diagrams are these behaviours in the abstract, with entries and exits marked by labels. The item is the monoid they form under the product modelled on concatenation, together with two pieces of structure on it: reflection, which mirrors a diagram, and edge inclusion.
Diagrams and Their Product
Fix a set of labels and two copies and of it: positive labels mark crossings to the right, negative labels crossings to the left. A diagram on labels is a quadruple of relations (1)✦ the forward, backward, left and right relations of , whose pairs are the edges of : an edge of enters on the left and exits on the right, an edge of enters on the right and exits on the left, an edge of enters and exits on the left, and an edge of enters and exits on the right.
Relations compose in path order: for and , the product holds when and for some . The reflexive transitive closure of a relation on a set is the relation on (2)✦ where is the identity relation on and .
The product of diagrams and on labels is the diagram on labels with (3)✦
The identity diagram is the diagram on labels with (4)✦
The reflection of a diagram on labels is the diagram on labels with (5)✦ where a label of stands for the label of of the same name, and conversely.
Edge inclusion is the relation on diagrams on labels in which when (6)✦
The Claim
Definition 1 (The diagram monoid ). The diagram monoid is the set of diagrams on labels with the product (3) and the identity diagram . For diagrams , and on labels, the product is associative, (7)✦ the identity diagram is a unit on the left, (8)✦ and on the right, (9)✦ and reflection reverses products, (10)✦ If , , and are diagrams on labels with and , then (11)✦
In the paper, the result reads: a diagram is four relations , , and on disjoint label sets and of size ; the product is given by the four formulas (2.2); the identity has and the identity and and empty; these diagrams form a finite monoid ; is componentwise inclusion and is preserved by products; and reflection exchanges with and with and reverses products.
What Is Checked
The claim is stated over diagrams on labels (1), their product (3) with the reflexive transitive closure (2), the identity diagram (4), reflection (5) and edge inclusion (6).