Deciding unique decodability of bigram counts via finite automata
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