Complexity of Regular Functions

Book chapter

Peer reviewed

Eric Allender and Ian Mertz

Language and Automata Theory and Applications, pp.449-460

Lecture Notes in Computer Science, Springer International Publishing

02/24/2015

Abstract

Computational complexity

Transducers

Weightedautomata

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

5 Record Views

Title: Complexity of Regular Functions
Creators: Eric Allender - Department of Computer Science, Rutgers University, Piscataway, USA
Ian Mertz - Department of Computer Science, Rutgers University, Piscataway, USA
Publication Details: Language and Automata Theory and Applications, pp.449-460
Date published: 02/24/2015
Series: Lecture Notes in Computer Science
Publisher: Springer International Publishing; Cham
Academic Unit: Computer Science (SAS)
Language: English
Resource Type: Book chapter
Identifiers: 991031653982404646