Complexity of Regular Functions

Accepted manuscript

Open access

Peer reviewed

Eric Allender and Ian Mertz

Lecture Notes in Computer Science, Vol.8977, pp.449-460

LATA 2015 (Nice, France, 2015)

2015

DOI:

https://doi.org/10.7282/T31J9CND

Abstract

Computational complexity

Transducers

Weighted automata

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

pdf

cra208.52 kBDownload View

Accepted Manuscript Open Access

url

http://dx.doi.org/doi:10.1007/978-3-319-15579-1_35View

Lecture Notes in Computer Science

url

http://link.springer.com/book/10.1007/978-3-319-15579-1View

url

Report an accessibility issueView

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

340 File downloads

65 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: Lecture Notes in Computer Science, Vol.8977, pp.449-460
Conference: LATA 2015 (Nice, France, 2015)
Date published: 2015
Publisher: Springer Verlag
Number of pages: 17 p.
Grant note: National Science Foundation - CCF-1064785
Academic Unit: School of Arts and Sciences; Computer Science (SAS)
Language: English
Resource Type: Accepted manuscript
Identifiers: 991031550246204646