View in EDS

Synchronizing finite automata with short reset words

Saved in:
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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 36563717
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Synchronizing finite automata with short reset words
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Roman%2C+Adam%22">Roman, Adam</searchLink><relatesTo>1</relatesTo><i> roman@ii.uj.edu.pl</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Applied+Mathematics+%26+Computation%22">Applied Mathematics & Computation</searchLink>. Mar2009, Vol. 209 Issue 1, p125-136. 12p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Sequential+machine+theory%22">Sequential machine theory</searchLink><br /><searchLink fieldCode="DE" term="%22Synchronization%22">Synchronization</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+sequences%22">Mathematical sequences</searchLink><br /><searchLink fieldCode="DE" term="%22Heuristic+programming%22">Heuristic programming</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=36563717
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.amc.2008.06.019
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 12
        StartPage: 125
    Subjects:
      – SubjectFull: Sequential machine theory
        Type: general
      – SubjectFull: Synchronization
        Type: general
      – SubjectFull: Mathematical sequences
        Type: general
      – SubjectFull: Heuristic programming
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Polynomials
        Type: general
    Titles:
      – TitleFull: Synchronizing finite automata with short reset words
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Roman, Adam
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 03
              Text: Mar2009
              Type: published
              Y: 2009
          Identifiers:
            – Type: issn-print
              Value: 00963003
          Numbering:
            – Type: volume
              Value: 209
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Applied Mathematics & Computation
              Type: main
ResultId 1