Insertion operations on deterministic reversal-bounded counter machines

作者：

Highlights：

• Insertions on deterministic reversal-bounded multicounter machines (DCM) are studied.

• DCMs with 2 counters are not closed under right concatenation with the universe.

• For left concatenation, only 1 counter that makes 1 reversal is needed for non-closure.

• The right input end-marker is necessary for DCM as opposed to deterministic pushdowns.

• DCM is closed under inverse deterministic transducers augmented by counters.

摘要

•Insertions on deterministic reversal-bounded multicounter machines (DCM) are studied.•DCMs with 2 counters are not closed under right concatenation with the universe.•For left concatenation, only 1 counter that makes 1 reversal is needed for non-closure.•The right input end-marker is necessary for DCM as opposed to deterministic pushdowns.•DCM is closed under inverse deterministic transducers augmented by counters.

论文关键词：Automata and logic,Counter machines,Insertion operations,Reversal-bounds,Determinism,Finite automata

论文评审过程：Received 19 June 2015, Revised 8 September 2017, Accepted 4 February 2018, Available online 5 March 2018, Version of Record 6 June 2019.

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