Volume 19, No 4, 2012, P. 8698
UDC 519.7
S. S. Marchenkov
On solutions to systems of automatatype functional equations
Abstract:
The automatatype functional equations are considered. These equations include subject variables for natural numbers and oneplaced functional variables for infinite binary sequences. An algorithm is defined which solves the satisfiability problem for finite systems of functional equations containing only functions 1 and t + 1. The linear homogeneous structures are used to establish the lower bound for time complexity of similar deciding algorithms. It is proved that the satisfiability problem is algorithmically undecidable for the systems of functional equations which contain yet the functions 2t, 3t, and 5t.
Tab. 1, bibliogr. 10.
Keywords: automatatype functional equation, satisfiability problem.
Marchenkov Sergei Seraphimovich ^{1}
1. Lomonosov Moscow State University,
Leninskie gory, 119991 Moscow, Russia
email: ssmarchen@yandex.ru
