On automaton determinisation of sets of superwords
A. G. Verenikin, E. E. Gasanov · Discrete Mathematics and Applications · 2006
We introduce the concept of a determinising automaton which, for every superword taken from a given set fed into its input, beginning with some step, at any time t yields the value of the input word at time t + 1, that is, predicts the input superword. We find a criterion whether a given set of superwords is determinisable, that is, whether for the set there exists a determinising automaton. We give the best (in some sense) method to design a determinising automaton for an arbitrary determinisable set of superwords. For some determinisable sets we present optimal and asymptotically optimal determinising automata.