2021, issue 1, p. 43-53
Received 18.01.2021; Revised 19.02.2021; Accepted 25.03.2021
Published 30.03.2021; First Online 03.04.2021
https://doi.org/10.34229/2707-451X.21.1.4
Previous | Full text (in Ukrainian) | Next
A New Approach to Solving the Problem of Generating Sets of Complex Structural Objects Based on a Quasi-Equivalent Transformation of a Labeling Scheme
Igor
Tkachov 
Scientific and Training center for Applied Informatics of the NAS of Ukraine, Kyiv
Correspondence: tThis email address is being protected from spambots. You need JavaScript enabled to view it.
The paper presents the results of a theoretical study related to the development of methods for constructing generating structures based on labeling schemes for generating sets of complex structural objects. In a theoretical aspect, generated objects are mappings of sets of objects into a set of labels, and in practical terms, they can be, in particular, visual images. The scientific and practical interest in generative constructions is that they can be used to determine whether objects belong to a certain class, that is, to solve the problem of pattern recognition.
The problem of constructing generating labeling scheme belongs to a wide section of modern applied informatics that embraces Constraint Satisfaction Problem and related themes [1–4]. But this problem has not been posed before and there are still no regular methods for solving it.
The analysis of the above methods is based on the formalism of the consistent labeling problem [6, 10, 11], which is, on the one hand, a generalization of many statements of discrete problems of Constraint Satisfaction, and, on the other hand, a transparent theoretical construction with a well-developed mathematical foundation.
The problem of constructing a relational scheme (in this case, labeling scheme) that generates a given set of mappings, by analogy with linguistic models, may be named “the problem of grammar restoration” [12–14].
In previous studies it was shown that to solve this problem it makes sense to use equivalent transformations of the labeling scheme [11]. This is because the source table listing all the complex objects that should be generated by the target scheme is itself a trivial variant of the scheme with a given set of consistent labelings. This means that the source scheme and target scheme are equivalent. However, one of the equivalent operations – disunion of a column – cannot be used regularly, since it requires certain conditions to be met regarding the internal structure of the column.
In this case, to expand the capabilities of four known equivalent transformations of the labeling scheme – deleting and appending nonexistent labeling, as well as joining of columns and column disunion – a non-equivalent transformation was added – "coloring the column labelings".
The purpose of the paper is to introduce and investigate operation of "coloring the column labelings" that leads to a non-equivalent transformation of a labeling scheme. Show the advisability of using the known equivalent and the introduced quasi-equivalent transformations of the labeling scheme to solve the problem of constructing generating structures based on labeling schemes.
Results. The transformation of the labeling scheme, called "coloring the labelings of the scheme column", has been introduced. It is shown that its implementation leads to a quasi-equivalent labeling scheme, by solving which it is possible to uniquely restore the solution of the original problem. A method is proposed for using the newly introduced operation to transform the labeling scheme into a quasi-equivalent labeling scheme, in which it becomes possible to regularly perform the column decoupling operation. This ability of the operation of "coloring the column labelings" opens the way to the creation of a method for solving the problem of restoring a labeling scheme that generates a given set of consistent labelings.
Keywords: relational scheme, consistent labeling scheme, equivalent labeling scheme transformations, constraint satisfaction problem.
Cite as: Tkachov I. A New Approach to Solving the Problem of Generating Sets of Complex Structural Objects Based on a Quasi-Equivalent Transformation of a Labeling Scheme. Cybernetics and Computer Technologies. 2021. 1. P. 43–53. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.1.4
References
1. Dechter R. Constraint processing. San Francisco: Morgan Kaufmann, 2003. 481 p.
2. Freuder E.C., Mackworth A.K. Constraint satisfaction: An emerging paradigm. Foundations of Artificial Intelligence. 2006. 2. P. 13–27. https://doi.org/10.1016/S1574-6526(06)80006-4
3. Tsang E. Foundations of Constraint Satisfaction. New York: Academic Press, 1993. 421 p.
4. Handbook of Constraints Programming. Elsevier B.V. 2006. 955 p.
5. Tkachov I.I. Special structures in labeling schemes. ІІ Int. conf. «The role of innovations in transformation of the modern science». Kyiv: Inst. of innovative education. 2018. P. 213–222. (in Ukrainian) https://novaosvita.com/wp-content/uploads/2019/01/InnTrImModSc-Kyiv-Dec2018_v1.1.pdf
6. Tkachov I.I. Relational methods of pattern recognition and the problem of algebraic models homomorphism. Doklady AN Ukrainskoy SSR, Ser. А. 1988. 1. P. 76–78. (in Russian)
7. Tkachov I.I. Relational models for description of structures of complex objects in pattern recognition. Int. conf. «Science, education, society». Odessa: «IOMP». 2016. P. 164–169. (in Ukrainian) https://en.calameo.com/read/0031683720c8ede790c06
8. Tkachov I.I. Consistent labelings and homoorphisms of relations in problems of analysis of complex objects structures. ІІ Int. conf. «Science, education, society»». Kyiv: Inst. of innovative education. 2016. P. 187–192. https://ru.calameo.com/read/0031683726793adec3caa
9. Tkachov I.I. Relational methods of pattern recognition: two fundamental formulations of the problem. In Proceedings of intern. conf. "Mathematical methods of image recognition". Kyiv: Institute of cybernetics of NACU. 1991, P. 32–34. (in Russian)
10. Haralick R.M. Scene Matching Problems. Digital image processing and analysis: NATO advanced study institute. 1978. P. 184–202.
11. Tkachev I.I. Equivalent transformations in one class of recognition systems. Cybern Syst Anal. 1981. 17. P. 29–35. https://doi.org/10.1007/BF01307033
12. Tkachov I.I. Transformation of relational schemes and the “grammar restoration” problem». In Proceedings of intern. conf. “Modern informatics: problems, achievements and prospects”. Kyiv: Institute of cybernetics of NACU. 2017. P. 154–157. https://ru.calameo.com/read/0031683724703e37cfd96
13. Tkachov I.I. Generative possibilities of relational schemes. In Proceedings of intern. conf. "Computational intelligence (Results, problems, prospects)" Uzhorod: MESU and others. 2019. P. 131–132. https://en.calameo.com/read/003168372f07dda801899
14. Tkachov I.I. About the model of constructive generation of the sets of complex objects on the basis of relational schemes. In Proceedings of V intern. conf. "Open evolving systems". Кyiv. 2020. P. 203–205. https://ru.calameo.com/read/0031683726ecb6303d80a
15. Fu K.S. Syntactic Methods in Pattern Recognition. Academic Press. NY. 1974. 397 p.
16. Shlezinger M.I. Syntactic analysis of two-dimensional visual signals in the presence of noise. Cybern Syst Anal. 1976. 12. P. 612–628. https://doi.org/10.1007/BF01070399
17. Shlezinger M.I. Mathematical tools for image processing. Kyiv: Naukova dumka, 1989. 200 p. (in Russian)
18. Minsky M., Papert S. Perceptrons: An Introduction to Computational Geometry. MIT Press. Cambridge, Mass, 1988. 292 p.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | Full text (in Ukrainian) | Next