Open AccessCOMBINATORIAL RECONSTRUCTION OF TWO-DIMENSIONAL WORDS IN THE HYPOTHESIS SHIFT 1
Author(s) -
Mikhail Ulyanov
Publication year - 2021
Publication title -
nacionalʹnaâ associaciâ učënyh/nacionalʹnaâ associaciâ učenyh
Language(s) - English
Resource type - Journals
eISSN - 2782-2869
pISSN - 2413-5291
DOI - 10.31618/nas.2413-5291.2021.1.73.495
Subject(s) - multiset , window (computing) , word (group theory) , mathematics , eulerian path , algorithm , combinatorics , computer science , geometry , lagrangian , operating system
The article considers the formulation of the problem of reconstruction of two-dimensional words by a given multiset of subwords, under the hypothesis that this subset is generated by the displacement of a two-dimensional window of fixed size by an unknown two-dimensional word with a shift 1. A variant of the combinatorial solution of this reconstruction problem is proposed, based on a two-fold application of the one-dimensional word reconstruction method using the search for Eulerian paths or cycles in the de Bruyne multiorgraph. The efficiency of the method is discussed under the conditions of a square two-dimensional shift window one having a large linear size.