Bibliographic Details
| Title: |
Synchronizing finite automata with short reset words |
| Authors: |
Roman, Adam1 roman@ii.uj.edu.pl |
| Source: |
Applied Mathematics & Computation. Mar2009, Vol. 209 Issue 1, p125-136. 12p. |
| Subjects: |
Sequential machine theory, Synchronization, Mathematical sequences, Heuristic programming, Algorithms, Polynomials |
| Abstract: |
Abstract: Finding synchronizing sequences for finite automata is a very important problem in many practical applications (part orienters in industry, reset problem in biocomputing theory, network issues, etc.). Problem of finding the shortest synchronizing sequence is NP-hard, so polynomial algorithms probably can work only as heuristic ones. In this paper we propose two versions of polynomial algorithms which work better than well-known Eppstein’s greedy algorithm and it is modification, a cycle algorithm, introduced by Trahtman. [Copyright &y& Elsevier] |
|
Copyright of Applied Mathematics & Computation is the property of Elsevier B.V. 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 |
