Sign in
Back
Complexity of regular functions
Journal article   Peer reviewed

Complexity of regular functions

Eric Allender and Ian Mertz
Journal of computer and system sciences, Vol.104, pp.5-16
09/2019
DOI: https://doi.org/10.1016/j.jcss.2016.10.005

Abstract

Weighted automata Computational complexity Transducers
We give complexity bounds for various classes of functions computed by cost register automata. •Complexity bounds are given for “Cost Register Automata” (CRA) functions.•CRA(Z,+) functions are in GapNC1; this bound is tight.•“Copyless” CRAs over the most common monoids are in NC1. This bound is tight.

Metrics

7 Record Views
2 Times Cited - Web of Science

Details