Tools for description of bounds for word variable values are offered. The use of these descriptions provides the conditions of a problem belonging to the class P or to the class NP. NP-completeness of some unification problems are proved. The validity of the proved bounds may make possible to create effective algorithms for unification of word terms, used in such programming language as Refal.
Original language
English
Title of host publication
Proceedings of the Seventh IEEE International Conference on Intelligent Computing and Information Systems, ICICIS 2015
Pages
56 – 57
State
Published - 2015
Externally published
Yes
Research areas
Equation in words, unification, polynomial-time complexity, NP-complete problem.
