Predictable semiautomata

AbstractWe introduce a new class of nondeterministic semiautomata: A nondeterministic semiautomaton S is predictable if there exists k≥0 such that, if S knows the current input a and the next k inputs, the transition under a can be made deterministically. Nondeterminism may occur only when the length of the unread input is ≤k. We develop a theory of predictable semiautomata. We show that, if a semiautomaton with n states is k-predictable, but not (k−1)-predictable, then k≤(n2−n)/2, and this bound can be reached for a suitable input alphabet. We characterize k-predictable semiautomata, and introduce the predictor semiautomaton, based on a look-ahead semiautomaton. The predictor is essentially deterministic and simulates a nondeterministic semiautomaton by finding the set of states reachable by a word w, if it belongs to the language L of the semiautomaton (i.e., if it defines a path from an initial state to some state), or by stopping as soon as it infers that w∉L. Membership in L can be decided deterministically