#
Problem 60: Minimal Absent Words

Words that do not occur in files provide a useful technique to discard or
discriminate files.
They act like the set of factors of a file but admit a
more compact trie representation as factor codes.

A word $w$, $|w|\gt 1$, is said to be absent or forbidden in a word $x$ if it
does not occur in $x$.
It is said to be minimal with this property if in
addition both $w[0\dd |w|-2]$ and $w[1\dd |w|-1]$ do occur in $x$.

A natural method to compute the minimal words absent in $x$ is to start with
its Factor automaton $\aFact(x)$, smallest deterministic automaton accepting
all its factors.
Each factor is spelt out along a path starting from the
initial state and all states are terminal.

Design a linear-time algorithm to compute the trie of minimal absent words of
a word $x$ from its Factor automaton $\aFact(x)$.

Use failure links of the automaton.

Design a linear-time algorithm to recover the Factor automaton of a word $x$
from the trie of its minimal absent words.

Use the Aho-Corasick technique.

## References

A. V. Aho and M. J. Corasick. Efficient string matching: An aid to
bibliographic search. *Commun. ACM*, **18**(6):333-340, 1975.
M. Béal, F. Mignosi, and A. Restivo. Minimal forbidden words and
symbolic dynamics. In C. Puech and R. Reischuk, editors, *STACS 96,
13th Annual Symposium on Theoretical Aspects of Computer Science,
Grenoble, France, February 22-24, 1996, Proceedings*, volume 1046 of
Lecture Notes in Computer Science, pages 555-566. Springer, 1996.
M.-P. Béal, M. Crochemore, F. Mignosi, A. Restivo, and M. Sciortino.
Forbidden words of regular languages. *Fundam. Inform.*, **56**(1,2):121-
135, 2003.
A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, and
J. I. Seiferas. The smallest automaton recognizing the subwords of a
text. *Theor. Comput. Sci.*, **40**:31-55, 1985.
S. Chairungsee and M. Crochemore. Using minimal absent words to
build phylogeny. *Theor. Comput. Sci.*, **450**(1):109-116, 2012.
M. Crochemore. Transducers and repetitions. *Theor. Comput. Sci.*,
**45**(1):63-86, 1986.
M. Crochemore, C. Hancart, and T. Lecroq. *Algorithms on Strings*.
Cambridge University Press, 2007. 392 pages.
M. Crochemore, A. Héliou, G. Kucherov, L. Mouchard, S. P. Pissis, and
Y. Ramusat. Absent words in a sliding window with applications. *Inf.
Comput.*, **270**, 2020.
M. Crochemore, F. Mignosi, and A. Restivo. Automata and forbidden
words. *Inf. Process. Lett.*, **67**(3):111-117, 1998.
M. Crochemore, F. Mignosi, A. Restivo, and S. Salemi. Text compression
using antidictonaries. In J. Wiedermann, P. van Emde Boas, and
M. Nielsen, editors, *International Conference on Automata, Languages
an Programming (Prague, 1999)*, number 1644 in LNCS, pages 261-270.
Springer-Verlag, 1999. Rapport I.G.M. 98-10, Université de Marne-la-
Vallée.
M. Crochemore and W. Rytter. *Text algorithms*. Oxford University
Press, 1994. 412 pages.
M. Crochemore and W. Rytter. *Jewels of Stringology*. World Scientific
Publishing, Hong-Kong, 2002. 310 pages.
T. Mieno, Y. Kuhara, T. Akagi, Y. Fujishige, Y. Nakashima, S. Inenaga,
H. Bannai, and M. Takeda. Minimal unique substrings and minimal
absent words in a sliding window. In A. Chatzigeorgiou, R. Dondi,
H. Herodotou, C. A. Kapoutsis, Y. Manolopoulos, G. A. Papadopoulos,
and F. Sikora, editors, *SOFSEM 2020: Theory and Practice of Computer
Science - 46th International Conference on Current Trends in Theory
and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January
20-24, 2020, Proceedings*, volume 12011 of Lecture Notes in Computer
Science, pages 148-160. Springer, 2020.
T. Ota, H. Fukae, and H. Morita. Dynamic construction of an antidictionary
with linear complexity. *Theor. Comput. Sci.*, **526**:108-119,
2014.
T. Ota and H. Morita. On a universal antidictionary coding for stationary
ergodic sources with finite alphabet. In *International Symposium
on Information Theory and its Applications*, ISITA 2014, Melbourne,
Australia, October 26-29, 2014, pages 294-298. IEEE, 2014.
T. Ota and H. Morita. A compact tree representation of an antidictionary.
*IEICE Transactions*, **100-A**(9):1973-1984, 2017.
R. M. Silva, D. Pratas, L. Castro, A. J. Pinho, and P. J. S. G. Ferreira.
Three minimal sequences found in ebola virus genomes and absent from
human DNA. *Bioinformatics*, **31**(15):2421-2425, 2015.