zbMATH — the first resource for mathematics

On automaton determinisation of sets of superwords. (English. Russian original) Zbl 1121.68070
Discrete Math. Appl. 16, No. 3, 229-243 (2006); translation from Diskretn. Mat. 18, No. 2, 84-97 (2006).
Summary: 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 automaton determinization. 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.

68Q45 Formal languages and automata
Full Text: DOI
[1] V. B. Kudryavtsev, S. V. Aleshin, and A. S. Podkolzin, Introduction to Automata Theory. Nauka, Moscow, 1985 (in Russian). · Zbl 0604.68058
[2] B. A. Trakhtenbrot and Ya. M. Barzdin, Finite Automata. Behavior and Synthesis. North Holland, Amsterdam, 1973.
[3] I. M. Vinogradov, Introduction to the Theory of Numbers. Pergamon Press, London, 1955.
[4] A. I. Kostrikin, Introduction to Algebra. Fundamental Structures of Algebra. Fizmatlit, Moscow, 2000 (in Russian). · Zbl 0969.08001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.