A polynomial time algorithm to infer sequential machines

✍ Scribed by Katsuhiko Takahashi; Akio Fujiyoshi; Takumi Kasai

• Publisher: John Wiley and Sons
• Year: 2002
• Tongue: English
• Weight: 999 KB
• Volume: 34
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.1184

✦ Synopsis

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