Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. I. Reconstruction without for bidden words1

Cybernetics and Systems Analysis. 2015. Vol. 50. No. 1. P. 148–156.

Smetanin Y. G., Ульянов М. В.

The problem of reconstruction of a word from a set of its subwords is considered. It is assumed that the set is generated by unit shifts of a fixed window along an unknown word. For the problem without constrains on the unknown word, a method of reconstruction is proposed based on the search for Euler paths or Euler cycles in a de Bruijn multidigraph. The search is based on symbolic multiplication of adjacency matrices with special operations of multiplication and addition of edge names. The method makes it possible to find reconstructed words and the number of reconstructions. © 2014 Springer Science+Business Media New York.

Ключевые слова: de Bruijn graph, Euler path, enumeration of paths, reconstruction of words graph, reconstruction without forbidden words, symbolic matrix multiplication