COMBINATORIAL RECONSTRUCTION OF TWO-DIMENSIONAL WORDS IN THE HYPOTHESIS SHIFT 1
DOI:
https://doi.org/10.31618/nas.2413-5291.2021.1.73.495Keywords:
two-dimensional words, de Bruyne multiorgraph, reconstruction of two-dimensional wordsAbstract
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.
References
Simiu E. Haoticheskie perehody v determinirovannyh i stohasticheskih sistemah. — M.: Fizmatlit, 2007. —208 s.
Afrajmovich V., Ugalde E., Urias H. Fraktalnye razmernosti dlya vremen vozvrasheniya Puankare. — M.- Izhevsk: Institut kompyuternyh issledovanij, R&C Dynamics, 2011. — 292 s.
Lind D., Marcus B. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, UK. 1995. — 495 pp.
Matematicheskie metody dlya analiza posledovatelnostej DNK. — M.: Mir, 1999. — 349 s.
Lothaire M. Combinatorics of Words. Encyclopedia of Mathematics and its Applications. // Addison-Wesley Publishing Co., Reading, Mass. 1983. Vol. 17. —228 pp. http://www-igm.univ-mlv.fr/~berstel/Lothaire/
Lothaire M. Algebraic Combinatorics on Words. Cambridge University Press. 2002. — 455 с. http://www-igm.univ-mlv.fr/~berstel/Lothaire/.
Lothaire M. Algebraic Combinatorics on Words. 2005. — 610 c.
Ulyanov M.V., Tarasevich Yu. Yu., Eserkepov A. V., Grigorieva I. V. Characterization of domain formation during random sequential adsorption of stiff linear k-mers onto a square lattice // Phys. Rev. E.— 2020.— Oct.— Vol. 102, Iss. 4.— P. 042119 DOI 10.1103/PhysRevE.102.042119
Diffusion-driven self-assembly of rodlike particles: Monte Carlo simulation on a square lattice [Text] / Nikolai I. Lebovka, Yuri Yu. Tarasevich, Volodymyr A. Gigiberiya, Nikolai V. Vygornitskii // Phys. Rev. E. — 2017. — May. — Vol. 95. — P. 052130.
Smetanin Yu.G., Uljanov M.V., Shulga M.M. On Calculating the Entropy of 2D words over a Finite Alphabet // Proceedings of 2018 International Conference on Engineering Technologies and Computer Science. EnT 2018, 20–21 March 2018, Moscow, Russia, pp. 82–85 ISBN-13: 978-1-5386-5589-4, DOI 10.1109/EnT.2018.00025
Ulyanov M. V., Smetanin Yu. G., Shulga M. M., Eserkepov A. V., Tarasevich Yu.Yu. Characterisation of diffusion-driven self-organisation of rodlike particles by means of entropy of generalised two-dimensional words // Journal of Physics: Conference Series. — 2018. — December. — Vol. 1141. — P. 012137 DOI 10.1088/1742-6596/1141/1/012137
Smetanin Y. G. , M. V. Ulyanov Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. I. Reconstruction without for bidden words // Cybernetics and Systems Analysis. January 2014, Vol. 50, Issue 1, pp 148-156.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
CC BY-ND
A work licensed in this way allows the following:
1. The freedom to use and perform the work: The licensee must be allowed to make any use, private or public, of the work.
2. The freedom to study the work and apply the information: The licensee must be allowed to examine the work and to use the knowledge gained from the work in any way. The license may not, for example, restrict "reverse engineering."
2. The freedom to redistribute copies: Copies may be sold, swapped or given away for free, in the same form as the original.
