R70-36 Maximin Automata
Stephen T. Hedetniemi · IEEE Transactions on Computers · 1970
A stationary maximin automaton is a system A = 〈S, U, f, h, F〉, where S and U are finite nonempty sets of states and inputs, respectively; F⊆S is a set of final states; f:S × U × S →[0, 1] can be imagined to be a transition relation which associates with every state s E S and input u E U a measure, 0≤ f(s,u,s') ≤ 1 that the next state is s', there being no constraint, for example, that the sum of these measures equals 1 for a given s and u. Similarly, the function h: S → [0, 1] defines something like an initial distribution, again with no constraints on the sum of all of the h(s)'s. What serves to distinguish maximin automata from other better known classes of automata is the manner in which the function f is extended to sequences of inputs x ∈ U*; this is defined as follows: