CLR cover
Previous problem

Problem 60: Minimal Absent Words

Next problem

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.