View in EDS

On the complexity of intersecting finite state automata and NL versus NP

Saved in:
Bibliographic Details
Title: On the complexity of intersecting finite state automata and NL versus NP
Authors: Karakostas, George1 karakos@mcmaster.ca, Lipton, Richard J.2,3 rjl@cc.gatech.edu, Viglas, Anastasios4 aviglas@cs.toronto.edu
Source: Theoretical Computer Science. Jun2003, Vol. 302 Issue 1-3, p257. 18p.
Subjects: Algorithms, Machine theory
Abstract: We consider uniform and non-uniform assumptions for the hardness of an explicit problem from finite state automata theory. First we show that a small improvement in the known straightforward algorithm for this problem can be used to design faster algorithms for subset sum and factoring, and improved deterministic simulations for non-deterministic time.On the other hand, we can use the same improved algorithm for our FSA problem to prove complexity class separation results (NL is not equal to P, or NP for the non-uniform case). This result can be viewed either as a hardness result for the FSA intersection problem, or as a method for separating NL from P or NP. It is interesting to note that this approach is based on a more general method for separating two complexity classes, using algorithms rather than lower bounds. [Copyright &y& Elsevier]
Copyright of Theoretical Computer Science 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: 9856680
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On the complexity of intersecting finite state automata and <f>NL</f> versus <f>NP</f>
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Karakostas%2C+George%22">Karakostas, George</searchLink><relatesTo>1</relatesTo><i> karakos@mcmaster.ca</i><br /><searchLink fieldCode="AR" term="%22Lipton%2C+Richard+J%2E%22">Lipton, Richard J.</searchLink><relatesTo>2,3</relatesTo><i> rjl@cc.gatech.edu</i><br /><searchLink fieldCode="AR" term="%22Viglas%2C+Anastasios%22">Viglas, Anastasios</searchLink><relatesTo>4</relatesTo><i> aviglas@cs.toronto.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink>. Jun2003, Vol. 302 Issue 1-3, p257. 18p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Machine+theory%22">Machine theory</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We consider uniform and non-uniform assumptions for the hardness of an explicit problem from finite state automata theory. First we show that a small improvement in the known straightforward algorithm for this problem can be used to design faster algorithms for subset sum and factoring, and improved deterministic simulations for non-deterministic time.On the other hand, we can use the same improved algorithm for our FSA problem to prove complexity class separation results (<f>NL</f> is not equal to <f>P</f>, or <f>NP</f> for the non-uniform case). This result can be viewed either as a hardness result for the FSA intersection problem, or as a method for separating <f>NL</f> from <f>P</f> or <f>NP</f>. It is interesting to note that this approach is based on a more general method for separating two complexity classes, using algorithms rather than lower bounds. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Theoretical Computer Science 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=9856680
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/S0304-3975(02)00830-7
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 18
        StartPage: 257
    Subjects:
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Machine theory
        Type: general
    Titles:
      – TitleFull: On the complexity of intersecting finite state automata and <f>NL</f> versus <f>NP</f>
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Karakostas, George
      – PersonEntity:
          Name:
            NameFull: Lipton, Richard J.
      – PersonEntity:
          Name:
            NameFull: Viglas, Anastasios
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 13
              M: 06
              Text: Jun2003
              Type: published
              Y: 2003
          Identifiers:
            – Type: issn-print
              Value: 03043975
          Numbering:
            – Type: volume
              Value: 302
            – Type: issue
              Value: 1-3
          Titles:
            – TitleFull: Theoretical Computer Science
              Type: main
ResultId 1