Copyless cost-register automata: Structure, expressiveness, and closure properties

作者：

Highlights：

• A recently proposed model for computing functions copyless CRA is studied.

• It is shown that copyless CRA are not closed under reverse.

• A restricted variant bounded alternation CRA (BAC) is proposed.

• BAC is shown to be closed under reverse and other extensions.

摘要

•A recently proposed model for computing functions copyless CRA is studied.•It is shown that copyless CRA are not closed under reverse.•A restricted variant bounded alternation CRA (BAC) is proposed.•BAC is shown to be closed under reverse and other extensions.

论文关键词：Cost register automata,Weighted automata,Semirings

论文评审过程：Received 20 June 2017, Revised 27 July 2018, Accepted 30 July 2018, Available online 12 September 2018, Version of Record 19 November 2018.

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