Complexity of regular functions

作者：

Highlights：

• 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.

摘要

•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.

论文关键词：Computational complexity,Transducers,Weighted automata

论文评审过程：Received 5 June 2015, Revised 16 July 2016, Accepted 21 October 2016, Available online 2 November 2016, Version of Record 6 June 2019.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.10.005