A polynomial time algorithm to infer sequential machines.
Saved in:
| 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 ( |
| 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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 13380616 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A polynomial time algorithm to infer sequential machines. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Takahashi%2C+Katsuhiko%22">Takahashi, Katsuhiko</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Fujiyoshi%2C+Akio%22">Fujiyoshi, Akio</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Kasai%2C+Takumi%22">Kasai, Takumi</searchLink><relatesTo>1</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Systems+%26+Computers+in+Japan%22">Systems & Computers in Japan</searchLink>. 1/1/2003, Vol. 34 Issue 1, p59-67. 9p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Sequential+machine+theory%22">Sequential machine theory</searchLink><br /><searchLink fieldCode="DE" term="%22Input-output+analysis%22">Input-output analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+systems%22">Computer systems</searchLink><br /><searchLink fieldCode="DE" term="%22Machinery%22">Machinery</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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 (<URL>www.interscience.wiley.com</URL>). DOI 10.1002/scj.1184 [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=13380616 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1002/scj.1184 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 9 StartPage: 59 Subjects: – SubjectFull: Algorithms Type: general – SubjectFull: Sequential machine theory Type: general – SubjectFull: Input-output analysis Type: general – SubjectFull: Polynomials Type: general – SubjectFull: Computer systems Type: general – SubjectFull: Machinery Type: general Titles: – TitleFull: A polynomial time algorithm to infer sequential machines. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Takahashi, Katsuhiko – PersonEntity: Name: NameFull: Fujiyoshi, Akio – PersonEntity: Name: NameFull: Kasai, Takumi IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 01 Text: 1/1/2003 Type: published Y: 2003 Identifiers: – Type: issn-print Value: 08821666 Numbering: – Type: volume Value: 34 – Type: issue Value: 1 Titles: – TitleFull: Systems & Computers in Japan Type: main |
| ResultId | 1 |
