Staff View
Better Complexity Bounds for Cost Register Automata

Descriptive

TypeOfResource
Text
TitleInfo
Title
Better Complexity Bounds for Cost Register Automata
Name (type = personal); (authority = orcid); (authorityURI = http://id.loc.gov/vocabulary/identifiers/orcid.html); (valueURI = http://orcid.org/0000-0002-0650-028X)
NamePart (type = family)
Allender
NamePart (type = given)
Eric
Affiliation
Computer Science (New Brunswick), Rutgers University
Role
RoleTerm (type = text); (authority = marcrt)
author
Name (type = personal)
NamePart (type = family)
Krebs
NamePart (type = given)
Andreas
Affiliation
Universitaet Tuebingen
Role
RoleTerm (type = text); (authority = marcrt)
author
Name (type = personal)
NamePart (type = family)
McKenzie
NamePart (type = given)
Pierre
Affiliation
Universite de Montreal
Role
RoleTerm (type = text); (authority = marcrt)
author
Name (type = corporate); (authority = RutgersOrg-Department)
NamePart
Computer Science (New Brunswick)
Name (type = corporate); (authority = RutgersOrg-School)
NamePart
School of Arts and Sciences (SAS) (New Brunswick)
Genre (authority = RULIB-FS)
Article, Refereed
Genre (authority = NISO JAV)
Accepted Manuscript (AM)
Note (type = peerReview)
Peer reviewed
OriginInfo
DateIssued (encoding = w3cdtf); (keyDate = yes)
2018
Abstract (type = Abstract)
Cost register automata (CRAs) are one-way finite automata whose transitions have the side-effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the tropical semiring can simulate polynomial time computation, proving along the way that a naturally dened width-k circuit value problem over the tropical semiring is P-complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than NC^1 when the semiring is the integers, or strings with operations max and concat. This relates questions left open in recent work on the complexity of CRA-computable functions to long-standing class separation conjectures in complexity theory, such as NC versus P and NC^1 versus GapNC^1.
Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
PhysicalDescription
InternetMediaType
application/pdf
Extent
19 pages
Subject (authority = local)
Topic
Circuit Complexity
Subject (authority = local)
Topic
P-completeness
Subject (authority = local)
Topic
Cost-Register Automata
Extension
DescriptiveEvent
Type
Citation
DateTime (encoding = w3cdtf)
2018
AssociatedObject
Name
Theory of Computing Systems
Type
Journal
Relationship
Has part
Identifier (type = volume and issue)
Reference (type = url)
https://doi.org/10.1007/s00224-018-9871-4
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Originator
Name
Eric Allender
AssociatedObject
Type
Grant number
Name
CCF-1555409
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Originator
Name
Eric Allender
AssociatedObject
Type
Grant number
Name
CCF-1514164
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Originator
Name
Andreas Krebs
AssociatedObject
Type
Grant number
Name
KR 4042/2
RelatedItem (type = other version)
TitleInfo
Title
Better Complexity Bounds for Cost Register Automata
Identifier (type = doi)
https://doi.org/doi:10.7282/T3G73HTZ
Extension
DescriptiveEvent
Type
Version creation
DateTime (encoding = w3cdtf)
2018-08-21
Detail
Resource replaces author's original
AssociatedObject
Type
Journal article
Relationship
Is version of
Name
Better Complexity Bounds for Cost Register Automata
Identifier (type = doi)
https://doi.org/doi:10.7282/T3G73HTZ
Detail
Author's original
RelatedItem (type = host)
TitleInfo
Title
Allender, Eric
Identifier (type = local)
rucore30165700001
Location
PhysicalLocation (authority = marcorg); (displayLabel = Rutgers, The State University of New Jersey)
NjNbRU
Identifier (type = doi)
doi:10.7282/T38K7DGB
Back to the top

Rights

RightsDeclaration (AUTHORITY = FS); (TYPE = [FS] statement #1); (ID = rulibRdec0004)
Copyright for scholarly resources published in RUcore is retained by the copyright holder. By virtue of its appearance in this open access medium, you are free to use this resource, with proper attribution, in educational and other non-commercial settings. Other uses, such as reproduction or republication, may require the permission of the copyright holder.
Copyright
Status
Copyright protected
Availability
Status
Open
Reason
Permission or license
RightsEvent
Type
Permission or license
AssociatedObject
Type
License
Name
Multiple author license v. 1
Detail
I hereby grant to Rutgers, The State University of New Jersey (Rutgers) the non-exclusive right to retain, reproduce, and distribute the deposited work (Work) in whole or in part, in and from its electronic format, without fee. This agreement does not represent a transfer of copyright to Rutgers.Rutgers may make and keep more than one copy of the Work for purposes of security, backup, preservation, and access and may migrate the Work to any medium or format for the purpose of preservation and access in the future. Rutgers will not make any alteration, other than as allowed by this agreement, to the Work.I represent and warrant to Rutgers that the Work is my original work. I also represent that the Work does not, to the best of my knowledge, infringe or violate any rights of others.I further represent and warrant that I have obtained all necessary rights to permit Rutgers to reproduce and distribute the Work and that any third-party owned content is clearly identified and acknowledged within the Work.By granting this license, I acknowledge that I have read and agreed to the terms of this agreement and all related RUcore and Rutgers policies.
Back to the top

Technical

RULTechMD (ID = TECHNICAL1)
ContentModel
Document
CreatingApplication
Version
1.5
ApplicationName
MiKTeX pdfTeX-1.40.16
DateCreated (point = end); (encoding = w3cdtf); (qualifier = exact)
2018-05-09T16:32:27
DateCreated (point = end); (encoding = w3cdtf); (qualifier = exact)
2018-05-09T16:32:27
Back to the top
Version 8.3.10
Rutgers University Libraries - Copyright ©2019