Unique decodability of bigram counts by finite automata

Details Unique decodability of bigram counts by finite automata Unique decodability of bigram counts by finite automata

2011-11-28

arxiv.org/abs/1111.6431v1

Computer Science

Formal Languages and Automata Theory

12 pages

Scientific paper

We revisit the problem of deciding whether a given string is uniquely decodable from its bigram counts by means of a finite automaton. An efficient algorithm for constructing a polynomial-size nondeterministic finite automaton that decides unique decodability is given. Conversely, we show that the minimum deterministic finite automaton for deciding unique decodability has at least exponentially many states in alphabet size.

Affiliated with

Also associated with

No associations

Rating

Unique decodability of bigram counts by finite automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Unique decodability of bigram counts by finite automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unique decodability of bigram counts by finite automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-67545