Введение. Задача генерации полиномиальных инвриантов для произвольных полиномиально определенных программ, повидимому

Задача генерации полиномиальных инвриантов для произвольных полиномиально определенных программ, повидимому, является очень сложной. Ключевое место здесь – анализ циклов вида

X:= b;

While Q(X, b) do X:= F(X)

где - условие, - полиномиальное отображение . Пусть . Имеет смысл рассмотреть частные случаи

1. . Циклы с одной переменной в теле цикла

2. Циклы с линейным оператором в теле цикла.

L-инварианты линейных отображений и инварианты линейных циклов

Определение 1. Пусть - n-мерное векторное пространство над полем рациональных чисел и - алгебраическое замыкание поля. Обозначим через - мерный вектор переменных.Рациональная функция называется L -инвариантом линейного оператора , если для любого вектора имеет место соотношение

(1)

Дата добавления: 2014-01-20