Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-018 | 13th April 2015 21:48

Complexity of Regular Functions

RSS-Feed




Revision #1
Authors: Eric Allender, Ian Mertz
Accepted on: 13th April 2015 21:49
Downloads: 375
Keywords: 


Abstract:

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



Changes to previous version:

Complexity results dealing with the tropical semiring are extended and clarified.


Paper:

TR15-018 | 31st January 2015 16:05

Complexity of Regular Functions





TR15-018
Authors: Eric Allender, Ian Mertz
Publication: 31st January 2015 16:05
Downloads: 972
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint