пока l oop окончание в Дафни - PullRequest
Новая
       54

пока l oop окончание в Дафни

0 голосов
/ 15 марта 2020

Я пытаюсь проверить алгоритм, используя Дафни. Я изо всех сил пытаюсь исправить сообщение об ошибке " уменьшает выражение может не уменьшаться (тайм-аут) ". Базовая c структура моего алгоритма выглядит следующим образом: 

while (U != {})
    decreases |S| - |B - U|;  // S is a constant and |B| <= |S|
    invariant U < B;  // U is a subset of B
{
    var u :| u in U;  // pick an element of u
    U := U - {u};  // remove the element

    while (...)
        invariant U < B;  // U is a subset of B
    {
        // modifies B and U but does not modify |B - U|
    }
}

S, B и U - все множества. S не изменяется вообще в алгоритме. Я доказал, что количество элементов B меньше или равно количеству элементов S, поэтому условие уменьшения связано с нулем.

После каждого присваивания либо B, либо U (во внутреннем, тогда как l oop) Я могу доказать, что | B - U | остается такой же. Однако этого недостаточно, мне нужен инвариант al oop во внутреннем пространстве, в то время как l oop говорит об этом, но я не знаю, как express это в Дафни. Я пробовал следующее, но это не решило проблему: 

invariant |old(B) - old(U)| == |B - U|;

(Примечание: я впервые использую Dafny, и я застрял на этой проблеме в течение недели, любые предложения будут быть полезным).

1 Ответ

1 голос
/ 16 марта 2020

По express, что внутренний l oop не влияет на значение |B - U|, вы можете сохранить значение |B - U| в переменной-призраке непосредственно перед внутренним l oop. Затем отметим эту призрачную переменную во внутреннем инварианте l oop. Например: 

ghost var previousCardinalityOfBminusU := |B - U|;
while (...)
  invariant |B - U| == previousCardinalityOfBminusU
{
  // ...
}

Вот еще несколько комментариев:

  • Если внутренний l oop не добавляет никаких элементов в U, то проще окончание metri c для внешнего l oop равно |U|. Затем вы захотите добавить al oop инвариант, такой как |U| <= prev, к внутреннему l oop, где prev - это призрачная переменная, которую вы установите на |U| непосредственно перед внутренним l oop.

  • У вас также есть план для подтверждения завершения внутреннего l oop?

  • Выражение U < B говорит, что U правильное подмножество B, но, может быть, это уже то, что вы имели в виду под комментарием "U это подмножество B"?

  • Ваше сообщение об ошибке также говорит "тайм-аут". Иногда может быть несколько причин тайм-аута, и, возможно, исправление одного также заботится о другом. Чтобы убедиться, что все остальное в порядке, я предлагаю вам временно позволить верификатору предположить, что завершение работает.

    Один из способов сделать это - (временно) пометить каждый l oop знаком decreases *, что говорит верификатор, с которым все в порядке с l oop не завершается. (Это также потребует от вас пометить любой вмещающий l oop и метод вложения decreases *.)

    Другой способ временно позволить верификатору предположить, что завершение работает, - использовать оператор assume. Например, для внешнего l oop вы можете сделать: 

    while U != {}
  // as before
{
  ghost var prev := |S| - |B - U|;
  // as before
  // inner loop as before
  assume |S| - |B - U| < prev; // give verifier the (possibly incorrect) assumption that the termination metric has gone down
}

    Это может обнаружить, есть ли и другие проблемы (которые ранее были замаскированы тайм-аутом), и они могут быть другими причина тайм-аута. Однако, если ваша программа проверяет правильно с этими допущениями, то это действительно доказательство завершения, которое вызывает тайм-аут. Затем вам нужно будет попытаться предоставить больше аргумента корректности для верификатора (я догадываюсь, что некоторый дополнительный инвариант на внутреннем l oop сделает свое дело).

...