This article is cited in 1 paper

A generalization of a Moore theorem

P. A. Panteleev

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: Distinguishing sequences for finite automata were first introduced in the classical paper of E. Moore and since that they have many applications in testing of sequential circuits and communication protocols. One of the basic tasks in the testing of finite automata is to identify the initial state of the automaton under investigation. Suppose we have a full description of a finite deterministic Mealy automaton and we know that its initial state is in some subset of its set of states. Then the state-identification problem is to find the initial state by a sequential application of input symbols to the automaton. In this talk we discuss the bounds on the length of such input sequences and show a relation of this problem to combinatorial problems in hypergraph theory.

Keywords: Finite automaton, adaptive distinguishing sequence, Moore theorem, hypergraph.