View in EDS

Forward and backward synchronizing algorithms.

Saved in:
Bibliographic Details
Title: Forward and backward synchronizing algorithms.
Authors: Roman, Adam1 roman@ii.uj.edu.pl, Szykuła, Marek2 msz@cs.uni.wroc.pl
Source: Expert Systems with Applications. Dec2015, Vol. 42 Issue 24, p9512-9527. 16p.
Subjects: Machine theory, Synchronization, Electric circuits, Error-correcting codes, Polynomial time algorithms
Abstract: Automata synchronization has many important applications, mostly in conformance testing of electrical circuits, self-correcting codes and protocol testing. Finding a shortest synchronizing word cannot be done in polynomial time, assuming P ≠ NP. In some situations, especially for very large automata, finding such a word is almost impossible. Therefore, we accept any synchronizing word that is reasonably short and can be calculated in short time. The existing algorithms are either polynomial (quick, but not optimal) or exponential (exact, but useless in case of large automata). In this paper we present a flexible algorithmic framework for synchronization. It allows the user to parameterize the algorithm to obtain a desired balance in terms of a trade-off between memory usage, runtime and optimality. We also discuss many practical issues that affect efficiency of an implementation. In particular, we design a new polynomial backward algorithm, which works significantly better than previously used heuristic algorithms. Finally, we present detailed results of experiments involving automata up to 2000 states, which compare our algorithms in various settings and the other known algorithms, and check the impact of different parameters on the results. [ABSTRACT FROM AUTHOR]
Copyright of Expert Systems with Applications is the property of Pergamon Press - An Imprint of Elsevier Science 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: 109914852
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Forward and backward synchronizing algorithms.
– 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><br /><searchLink fieldCode="AR" term="%22Szykuła%2C+Marek%22">Szykuła, Marek</searchLink><relatesTo>2</relatesTo><i> msz@cs.uni.wroc.pl</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Expert+Systems+with+Applications%22">Expert Systems with Applications</searchLink>. Dec2015, Vol. 42 Issue 24, p9512-9527. 16p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Machine+theory%22">Machine theory</searchLink><br /><searchLink fieldCode="DE" term="%22Synchronization%22">Synchronization</searchLink><br /><searchLink fieldCode="DE" term="%22Electric+circuits%22">Electric circuits</searchLink><br /><searchLink fieldCode="DE" term="%22Error-correcting+codes%22">Error-correcting codes</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomial+time+algorithms%22">Polynomial time algorithms</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Automata synchronization has many important applications, mostly in conformance testing of electrical circuits, self-correcting codes and protocol testing. Finding a shortest synchronizing word cannot be done in polynomial time, assuming P ≠ NP. In some situations, especially for very large automata, finding such a word is almost impossible. Therefore, we accept any synchronizing word that is reasonably short and can be calculated in short time. The existing algorithms are either polynomial (quick, but not optimal) or exponential (exact, but useless in case of large automata). In this paper we present a flexible algorithmic framework for synchronization. It allows the user to parameterize the algorithm to obtain a desired balance in terms of a trade-off between memory usage, runtime and optimality. We also discuss many practical issues that affect efficiency of an implementation. In particular, we design a new polynomial backward algorithm, which works significantly better than previously used heuristic algorithms. Finally, we present detailed results of experiments involving automata up to 2000 states, which compare our algorithms in various settings and the other known algorithms, and check the impact of different parameters on the results. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Expert Systems with Applications is the property of Pergamon Press - An Imprint of Elsevier Science 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=109914852
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.eswa.2015.07.071
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 16
        StartPage: 9512
    Subjects:
      – SubjectFull: Machine theory
        Type: general
      – SubjectFull: Synchronization
        Type: general
      – SubjectFull: Electric circuits
        Type: general
      – SubjectFull: Error-correcting codes
        Type: general
      – SubjectFull: Polynomial time algorithms
        Type: general
    Titles:
      – TitleFull: Forward and backward synchronizing algorithms.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Roman, Adam
      – PersonEntity:
          Name:
            NameFull: Szykuła, Marek
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 30
              M: 12
              Text: Dec2015
              Type: published
              Y: 2015
          Identifiers:
            – Type: issn-print
              Value: 09574174
          Numbering:
            – Type: volume
              Value: 42
            – Type: issue
              Value: 24
          Titles:
            – TitleFull: Expert Systems with Applications
              Type: main
ResultId 1