Bibliographic Details
| Title: |
A polynomial time algorithm to infer sequential machines. |
| Authors: |
Takahashi, Katsuhiko1, Fujiyoshi, Akio2, Kasai, Takumi1 |
| Source: |
Systems & Computers in Japan. 1/1/2003, Vol. 34 Issue 1, p59-67. 9p. |
| Subjects: |
Algorithms, Sequential machine theory, Input-output analysis, Polynomials, Computer systems, Machinery |
| 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 [ABSTRACT FROM AUTHOR] |
|
Copyright of Systems & Computers in Japan is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
