The Setting
Take a set and use the binary relations on as letters. A word then lays out a route of steps through , the th step allowed from to when , and the words of interest are those along which some walk in completes every step. The question is how few states suffice for a two-way nondeterministic finite automaton (2NFA) that recognizes these words when is finite.
The Source Language
For a set , the monoid of binary relations on is the set of all binary relations on under the path-order product, in which when and for some , with the identity relation as its identity. The relation product of a word over the alphabet is the product of its letters in order: (1)✦
The source language over is the set of words whose relation product is nonempty: (2)✦
Two-way Automata
A two-way nondeterministic finite automaton over an alphabet with state set , both of which may be infinite, consists of an initial state , a set of accepting states and a transition function .✦ To each state and each tape symbol , a letter of or one of the endmarkers and , the transition function assigns a set of pairs of a next state and a head move, left, stay or right.
For a word over , the tape symbol at a cell of the tape, numbered from to , is (3)✦ A configuration of on is a pair of a state and a cell. The one-step relation of on is the relation on configurations given by (4)✦ Both configurations lie on the tape, so no step moves the head past an endmarker. The reflexive transitive closure of the one-step relation is the union of its powers for , the zeroth being the identity relation on configurations.✦
The language of is the set of words over on which a run from the initial state on the left endmarker reaches an accepting state: (5)✦
The Source Automaton
For a set , the source automaton is the 2NFA over whose states are the points of and two further states, an initial state and a state , the only accepting one, and whose transition function is given, for and , by (6)✦ and by the empty set on every other pair of a state and a tape symbol.
The Claim
Theorem 1. Let be a set. Then (7)✦ If is finite, there is a 2NFA over with exactly states such that (8)✦
In the paper, the result reads: the language is recognized by a 2NFA with exactly states.
What Is Checked
The claim is stated over 2NFAs and their languages (5), read on the tape (3) through the one-step relation (4) and its reflexive transitive closure, and over the relation product (1), the source language (2) and the source automaton (6).