Deciding unique decodability of bigram counts via finite automata

作者：

Highlights：

• We prove that the bigram-decodable strings form a regular language.

• We construct a cubic-sized NFA for recognizing this language.

• We show how to simulate this NFA efficiently.

• We give a lower bound on the size of any DFA for this language.

摘要

•We prove that the bigram-decodable strings form a regular language.•We construct a cubic-sized NFA for recognizing this language.•We show how to simulate this NFA efficiently.•We give a lower bound on the size of any DFA for this language.

论文关键词：Uniqueness,Sequence reconstruction,Eulerian graph,Finite-state automata

论文评审过程：Received 28 November 2011, Revised 23 August 2013, Accepted 18 September 2013, Available online 26 September 2013.

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