Complexity of Regular Functions

Accepted manuscript

Open access

Peer reviewed

Eric Allender and Ian Mertz

Journal of Computer and System Sciences

2016

DOI:

https://doi.org/10.7282/T3QC05RB

Abstract

Computational Complexity

Transducers

Weighted automata

We give complexity bounds for various classes of functions computed by cost register automata.

pdf

cra233.40 kBDownload View

Accepted Manuscript (AM) Open Access

url

http://dx.doi.org/10.1016/j.jcss.2016.10.005View

Version of Record (VoR) Journal of Computer and System Sciences

url

Report an accessibility issueView

Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

144 File downloads

68 Record Views

Title: Subtitle: Complexity of Regular Functions
Creators: Eric Allender (Author) - Computer Science (New Brunswick), Rutgers University
Ian Mertz (Author) - Computer Science (New Brunswick), Rutgers University
Publication Details: Journal of Computer and System Sciences
Date published: 2016
Publisher: Rutgers University
Number of pages: 20 p.
Grant note: National Science Foundation - CCF-1064785 ; National Science Foundation - CCF-1555409
Academic Unit: School of Arts and Sciences; Computer Science (SAS)
Language: English
Resource Type: Accepted manuscript
Identifiers: 991031549939304646