A polynomial time algorithm to infer sequential machines
Katsuhiko Takahashi, Akio Fujiyoshi, Takumi Kasai · Systems and Computers in Japan · 2002
Abstract In this paper, we will describe an algorithm which infers a Moore‐type sequential machine from examples of inputs and outputs of an unknown Moore‐type sequential machine. The hypothesis output by this inference algorithm is a nondeterministic Moore‐type sequential machine which does not conflict with the given examples of inputs and outputs; we will show that the update time of the hypothesis will become a polynomial time of the sum of the lengths of the examples of inputs and outputs. Moreover, we will show that this inference algorithm will identify the Moore‐type sequential machine in the limit by using the complete examples of inputs and outputs defined from the structures of the Moore‐type sequential machine. © 2002 Wiley Periodicals, Inc. Syst Comp Jpn, 34(1): 59–67, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/scj.1184