The Setting
The source gives an exponential lower bound on the number of states needed to complement a two-way nondeterministic finite automaton (2NFA), and this item belongs to its Section 4, An exponential bound for order-reversing images. The item’s claims concern a monoid seen in two ways: through binary relations on a finite set of points, and through boundary diagrams on labels, which record how a 2NFA with states can enter and leave a block of its tape.
The item is the induction on that proves Proposition 4.3 of the source, which bounds a count of classes of diagrams from below by the loss bound of . The loss bound of a natural number is the power of two (1)✦ with exponent for . The induction has a base case for and a step from points to points in three parts, and the library states the base case and the ten lemmas of the step as eleven separate claims.
The Relation Monoid
The relation monoid of a set is the monoid of all binary relations on under the path-order product, in which when and for some , with the identity relation as unit.✦ The restricted identity of a subset of is the relation on (2)✦ and the permutation unit of a permutation of is its graph, as an element of : (3)✦
The reflexive transitive closure of a relation on a set is the relation (4)✦ with the identity relation on .
Boundary Diagrams
A boundary diagram on labels is a quadruple of relations on two copies and of an -element set of labels: the forward relation , whose edges enter on the left and exit on the right; the backward relation , whose edges enter on the right and exit on the left; the left relation , whose edges enter and exit on the left; and the right relation , whose edges enter and exit on the right.✦ The set of boundary diagrams on labels is .
The product of diagrams is the diagram obtained by gluing to the left of : (5)✦
Edge inclusion is the relation on with when , , and .✦ The corner of a diagram is the set of diagrams in with .✦ The nesting order is the relation on with when and are idempotent and .✦
Recurrent and Missing Classes
For a sign , the through relation of a diagram is the relation on the labels given by for and by for .✦ The loop closure and the recurrence relation of a diagram at are the relations on the labels (6)
A signed recurrent class of a diagram is a pair of a sign and a set of labels for which some label with has (7)✦ The set of signed recurrent classes of is .
For diagrams and and a sign , the surviving relation of relative to at is , the through relation of closed on both sides by the loop closure of .✦ The set of classes of missing at holds the classes on which the surviving relation has no loop: (8)✦
The Claim
Theorem 1. Let be a monoid, a set, a monoid homomorphism and a map with for all .
Base case. Suppose order reversal holds: implies for all . If has at most 128 points and an element of has for points of , then (9)✦
Conjugation. For every unit of and every , (10)✦
Moving the edge. Suppose every permutation of has a unit of with . If is an idempotent of with for points of , and are points of , then some idempotent of has (11)✦
Hub and families. If is finite with at least 129 points, there are a point of , the hub, and two families and , each of 64 distinct points of , with (12)✦
Removing the hub. For points , , of with and , (13)✦
Common budget. Let be an idempotent of , and natural numbers, and elements of with for each among them. Then there is a set of at most classes, a common budget for all the elements , with (14)✦
Nested chain. Let be finite, an idempotent of , a natural number, a set of pairs of a sign and a set of labels, and elements of such that, for each , lies in the corner of and . Then extends to a sequence of idempotents of in which, for every , is a positive power of and , with for and (15)✦
Retained points. If is finite, and are disjoint subsets of with 64 points each, is a point of outside , and , then some subset of has (16)✦
Smaller instance. Let be finite and surjective. Let be an idempotent of and an element with , and let be a subset of and , points of with and . Then there are an idempotent of the corner and a monoid homomorphism from the corner monoid , with identity , onto such that is the restriction of to for every , every permutation of has a unit of with , and some idempotent of has (17)✦
Missing classes in context. Let , , , , be diagrams in with and idempotent, , in the corner of and in the corner of . Then (18)✦
Amplification. Let and be natural numbers, and natural numbers with and for every . Then (19)✦
In the paper, the result reads, with , and : in the base case, for , an empty missing set would give and contradict order reversal; in Step 1, conjugates and cost at most each, the cost of an element being the number of its missing classes, and the sandwiches have , for a fixed relation , and a common budget with ; in Step 2, the nested chain , whose -th step costs , has total cost ; and in Step 3, each step of the chain restricts to a smaller instance on points, so that and .
What Is Checked
The claims are stated over the relation monoid with its restricted identities (2) and permutation units (3), over the boundary diagrams of with their product (5), built with the closure (4), edge inclusion, corners and nesting, over the recurrent classes (7) of the relations (6) and the missing classes (8), and over the loss bound (1). The monoid and its maps enter (9), (10), (11), (14), (15) and (17); (18) concerns diagrams alone, (12), (13) and (16) points and subsets of , and (19) natural numbers.
The library proves that the permutation unit of a permutation of is a unit of , with inverse .✦