Deciding Whether two Codes Have the Same Ambiguities is in co-NP
Yannick Chevalier, Michaël Rusinowitch · 2022
We define a code to be a finite set of words C on a finite alphabet, and an ambiguity to be an equality between two words in the monoid C*. We recall that a code is uniquely decipherable if its ambiguities are trivial. In this paper we construct a finite-turn deterministic pushdown automaton that recognizes the set of ambiguities of a code. This allows one to show that whether two codes of the same size have the same ambiguities is in co-NP.