Vestnik Sankt-Peterburgskogo Universiteta. Seriya 10. Prikladnaya Matematika. Informatika. Protsessy Upravleniya
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Vestnik Sankt-Peterburgskogo Universiteta. Seriya 10. Prikladnaya Matematika. Informatika. Protsessy Upravleniya, 2017, Volume 13, Issue 3, Pages 250–263
DOI: https://doi.org/10.21638/11701/spbu10.2017.303
(Mi vspui336)
 

This article is cited in 5 scientific papers (total in 5 papers)

Applied mathematics

Extraction of a maximal common sub-formula of predicate formulas for the solving of some artificial intelligence problems

T. M. Kosovskaya, D. A. Petrov

St. Petersburg State University, 7–9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation
Full-text PDF (283 kB) Citations (5)
References:
Abstract: If an investigated object in an Artificial Intelligence problem is regarded as a set of its elements and is characterized by properties of these elements and relations between them, then a predicate calculus language is an adequate one for the description of an object and classes of objects. Such a way formalized problems are NP-complete or NP-hard. Example of such an NP-hard problem is the problem of the analysis of a complex object presented as a set of its elements and described by a set of atomic formulas with the predicates setting properties of these elements and relation between them. To solve such a problem, a problem of extraction of a maximal common up to the names of variables sub-formula of two elementary conjunctions of atomic predicate formulas is under consideration in the paper. Extraction of these sub-formulas allows us to reduce a recognition problem to a series of analogous problems with the less input data length by means of construction a level description of classes, which essentially decreases an exponent in the exponential upper bound for a number of solution algorithm steps for NP-hard problem of checking whether an object belongs to this class. An algorithm of extraction of a maximal common up to the names of variables sub-formula of two elementary conjunctions of atomic predicate formulas is presented in the paper. Bounds on number of the algorithm run number of steps are proved. The time of its implementation in dependence on the input data structure is analyzed. The analysis of the number of algorithm steps shows that the proposed algorithm may be successfully implemented in order to decrease computational complexity of many Artificial Intelligence problems which are formalized by means of predicate calculus. The results of numerical experiments show the influence of input data structure on the algorithm run time. For example, the increasing of amount of predicate arguments involves essential decreasing of the algorithm run time, which is a consequence of the recursion depth decreasing. The number of different predicate symbols occurred in the formula notation also essentially influences on the algorithm run time. At larger input data the effectiveness of the offered algorithm, cutting obviously unsuccessful “brunches”, is especially noticeable. The strong impact on the algorithm run time is exerted by distribution of variables as arguments of predicates. Results show its considerable decreasing at a nonuniform distribution of variables. During the described algorithm run a problem of checking the coincidence up to the names of variables (isomorphism) of two elementary conjunctions appears. This problem has the greatest computational complexity among the other problems arising on other steps of the algorithm. A polynomial algorithm of checking whether two elementary conjunctions of atomic predicate formulas coincide up to the names of variables (are isomorphic) is offered. The algorithm is not a precise one. The correctness of this algorithm implementation exceeds 99,5%. It is proved that if the algorithm gives a negative answer then the formulas are not isomorphic. If the algorithm gives a positive answer then the results of numerical experiments show that 99,5% pairs of formulas are isomorphic. Refs 14. Tables 2.
Keywords: Artificial Intelligence, predicate calculus, algorithmic complexity, isomorphism of predicate formulas.
Received: September 30, 2016
Accepted: June 8, 2017
Bibliographic databases:
Document Type: Article
UDC: 004.93.51
Language: Russian
Citation: T. M. Kosovskaya, D. A. Petrov, “Extraction of a maximal common sub-formula of predicate formulas for the solving of some artificial intelligence problems”, Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr., 13:3 (2017), 250–263
Citation in format AMSBIB
\Bibitem{KosPet17}
\by T.~M.~Kosovskaya, D.~A.~Petrov
\paper Extraction of a maximal common sub-formula of predicate formulas for the solving of some artificial intelligence problems
\jour Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr.
\yr 2017
\vol 13
\issue 3
\pages 250--263
\mathnet{http://mi.mathnet.ru/vspui336}
\crossref{https://doi.org/10.21638/11701/spbu10.2017.303}
\elib{https://elibrary.ru/item.asp?id=30102285}
Linking options:
  • https://www.mathnet.ru/eng/vspui336
  • https://www.mathnet.ru/eng/vspui/v13/i3/p250
  • This publication is cited in the following 5 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления
    Statistics & downloads:
    Abstract page:181
    Full-text PDF :45
    References:36
    First page:11
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024