On the completeness and supercompleteness of algorithmic models for comparing text fragments

G. V. Nikitov

Computing Center, Russian Academy of Sciences, ul. Vavilova 40, Moscow, 119991, Russia

Abstract: Within the framework of the algebraic approach to the synthesis of correct algorithms, a class of problems is studied in which the initial data consist of numerical descriptions of pairs of text fragments. Solution algorithms use these descriptions to classify the original pairs of fragments according to the degree of their similarity or dissimilarity. Solvability and regularity criteria for such problems were obtained in earlier studies. The special case of constructing monotone solutions to such problems was also studied. In this paper, criteria of the completeness and supercompleteness of algorithmic models for the class of problems under examination are proved. Criteria of the monotone completeness and supercompleteness are also considered.

Key words: algebraic approach to the synthesis of correct algorithms, solvability and regularity criteria, criterion of completeness and supercompleteness of algorithmic models.

UDC: 519.6+519.79

Received: 30.10.2008

 English version: Computational Mathematics and Mathematical Physics, 2009, 49:9, 1648–1652

Bibliographic databases:

• 
• 
•