On the complexity of the solution problem for linear equations over finite substitutions.


On the complexity of the solution problem for linear equations over finite substitutions.

Authors

Novikova T.A., Zakharov V.A.

Abstract

We found out the complexity of the solution problem for linear equations over a semigroup of finite substitutions and showed how to use the decision procedures for the analysis of the behaviour of sequential programs.

Full text of the paper in pdf (in Russian)

Keywords

substitution, equation, unification, logic-and-term equivalence, complexity

Research Group

Theoretical Computer Science

All publications during 2014 All publications