On the Completeness and Supercompleteness of AlgorithmicModels for Comparing Text Fragments

摘要

Within the framework of the algebraic approach to the synthesis of correct algorithms, aclass of problems is studied in which the initial data consist of numerical descriptions of pairs of textfragments. Solution algorithms use these descriptions to classify the original pairs of fragments accord-ing to the degree of their similarity or dissimilarity. Solvability and regularity criteria for such problemswere obtained in earlier studies. The special case of constructing monotone solutions to such problemswas also studied. In this paper, criteria of the completeness and supercompleteness of algorithmicmodels for the class of problems under examination are proved. Criteria of the monotone complete-ness and supercompleteness are also considered.