Линейная темпоральная логика к автомату Бюхи - Linear temporal logic to Büchi automaton

В формальная проверка, конечное состояние проверка модели нужно найти Büchi автомат (BA) эквивалент данной Линейная временная логика (LTL) формула, т.е. такая, что формула LTL и BA распознают одно и то же ω-язык. Есть алгоритмы, которые переводят формулу LTL в BA.[1][2][3][4] Это преобразование обычно выполняется в два этапа. Первый шаг производит обобщенный автомат Бюхи (GBA) из формулы LTL. Второй шаг переводит этот GBA в BA, который включает относительно легкая конструкция. Поскольку LTL строго менее выразительно, чем BA, обратное построение невозможно.

Алгоритмы преобразования LTL в GBA различаются стратегиями построения, но все они имеют общий базовый принцип, т.е. каждое состояние в построенном автомате представляет собой набор формул LTL, которые ожидал быть удовлетворенным оставшимся входным словом после появления состояния во время выполнения.

Переход с LTL на GBA

Здесь представлены два алгоритма построения. Первый обеспечивает декларативную и понятную конструкцию. Второй обеспечивает алгоритмическое и эффективное построение. Оба алгоритма предполагают, что входная формула f построена с использованием набора пропозициональных переменных AP и f находится в нормальная форма отрицания.Для каждой формулы LTL f 'без верхнего символа ¬ пусть негр(f ') = ¬f', негр(¬f ') = f'. Для частного случая f '=истинный, позволять негр(истинный) = ложный.

Декларативная конструкция

Прежде чем приступить к описанию конструкции, необходимо дать несколько вспомогательных определений. Для формулы LTL ж, Позволять cl(f) наименьший набор формул, удовлетворяющий следующим условиям:

  • истинный ∈ cl(е)
  • f ∈ cl(е)
  • если f1 ∈ cl(е) тогда негр(f1) ∈ cl(е)
  • если Икс ж1 ∈ cl(f) затем f1 ∈ cl(е)
  • если f1 ∧ f2 ∈ cl(f) затем f1, f2 ∈ cl(е)
  • если f1 ∨ f2 ∈ cl(f) затем f1, f2 ∈ cl(е)
  • если f1 U ж2 ∈ cl(f) затем f1, f2 ∈ cl(е)
  • если f1 р ж2 ∈ cl(f) затем f1, f2 ∈ cl(е)

cl(f) является замыканием подформул f при отрицании. Отметим, что cl(f) могут содержать формулы, которые не находятся в нормальной форме отрицания. cl(f) будут служить состояниями эквивалентного GBA. Мы стремимся построить GBA так, чтобы если состояние соответствует на подмножество M ⊂ cl(f) тогда GBA выполняет приемный прогон, начиная с состояния для слова, если и только если слово удовлетворяет каждой формуле в M и нарушает каждую формулу в cl(f) / M. По этой причине мы не будем рассматривать каждое множество формул M, которое явно несовместимо или входит в строго супермножество M ', такое что M и M' эквивалентны. Множество M ⊂ cl(f) является максимально последовательный если он удовлетворяет следующим условиям:

  • истинный ∈ M
  • ж1 ∈ M тогда и только тогда, когда ¬f1 ∉ M
  • ж1 ∧ f2 ∈ M тогда и только тогда, когда f1 ∈ M и f2 ∈ M
  • ж1 ∨ f2 ∈ M тогда и только тогда, когда f1 ∈ M или f2 ∈ M

Позволять cs(f) множество максимально согласованных подмножеств cl(f). Мы будем использовать только cs(f) как состояния GBA.

Строительство GBA

Эквивалент GBA к f это А= ({init} ∪cs(е), 2AP, Δ, {инициализация},F), куда

  • Δ = Δ1 ∪ Δ2
    • (M, a, M ') ∈ Δ1 если и только если (M '∩AP ) ⊆ a ⊆ {p ∈ AP | ¬p ∉ M '} и:
      • Икс ж1 ∈ M тогда и только тогда, когда f1 ∈ M ';
      • ж1 U ж2 ∈ M тогда и только тогда, когда f2 ∈ M или (f1 ∈ M и f1 U ж2 ∈ M ');
      • ж1 р ж2 ∈ M тогда и только тогда, когда f1 ∧ f2 ∈ M или (f2 ∈ M и f1 р ж2 ∈ M ')
    • Δ2 = {(init, a, M ') | (M '∩AP ) ⊆ a ⊆ {p ∈ AP | ¬p ∉ M '} и f ∈ M'}
  • Для каждого f1 U ж2 ∈ cl(f), {M ∈ cs(е) | ж2 ∈ M или ¬ (f1 U ж2) ∈ M} ∈ F

Три условия в определении Δ1 гарантировать, что любой запуск А не нарушает семантику временных операторов. Обратите внимание, что F - набор наборов состояний. F определены для захвата свойства оператора U что не может быть проверено путем сравнения двух последовательных состояний в серии, т. е. если f1 U ж2 верно в каком-то состоянии, то в конечном итоге f2 верно в каком-то состоянии позже.

Доказательство правильности приведенной выше конструкции

Пусть ω-слово ш= а1, а2, ... по алфавиту 2AP. Позволять шя = ая, ая + 1, ... .Пусть Mш = {f '∈ cl(е) | ш f '}, который мы называем удовлетворение set. В соответствии с определением cs(е), Мш ∈ cs(f). Можно определить последовательность ρш = init, Mш1, Мш2, .... Благодаря определению А, если w f, то ρш должен быть приемлемый пробег А над ш.

И наоборот, допустим А принимает ш.Пусть ρ = init, M1, М2, ... быть бегом А над шСледующая теорема завершает оставшееся доказательство корректности.

Теорема 1: Для всех i> 0 Mшя = Mя.

Доказательство: Доказательство проводится индукцией по структуре f '∈ cl(е).

  • Базовые случаи:
    • f '= истинный. По определениям f '∈ Mшя и f '∈ Mя.
    • f '= p. По определению А, p ∈ Mя тогда и только тогда, когда p ∈ aя тогда и только тогда, когда p ∈ Mшя.
  • Шаги индукции:
    • f '= f1 ∧ f2. Согласно определению согласованных множеств, f1 ∧ f2 ∈ Mя если и только тогда1 ∈ Mя и е2 ∈ Mя. По предположению индукции f1 ∈ Mшя и е2 ∈ Mшя. В силу определения удовлетворяющего множества f1 ∧ f2 ∈ Mшя.
    • f '= ¬f1, f '= f1 ∨ f2, f '= Икс ж1 или f '= f1 р ж2. Доказательства очень похожи на предыдущее.
    • f '= f1 U ж2. Доказательство равенства разделено на два доказательства вывода.
      • Если f1 U ж2 ∈ Mя, то f1 U ж2 ∈ Mшя. По определению переходов А, возможны следующие два случая.
        • ж2 ∈ Mя. По предположению индукции f2 ∈ Mшя. Итак, f1 U ж2 ∈ Mшя.
        • ж1 ∈ Mя и е1 U ж2 ∈ Mя + 1. И в связи с условием приемки А, существует хотя бы один индекс j ≥ i такой, что f2 ∈ Mj. Пусть j 'наименьший из этих индексов. Докажем результат индукцией по k = {j ', j'-1, ..., i + 1, i}. Если k = j ', то f2 ∈ Mk, мы применяем те же рассуждения, что и в случае f2 ∈ Mя. Если i ≤ k 2 ∉ Mk, и так f1 ∈ Mk и е1 U ж2 ∈ Mк + 1. По предположению индукции относительно f 'имеем f1 ∈ Mшk. В силу предположения индукции об индексах также имеем f1 U ж2 ∈ Mшк + 1. В силу определения семантики LTL, f1 U ж2 ∈ Mшk.
      • Если f1 U ж2 ∈ Mшя, то f1 U ж2 ∈ Mя. Из-за семантики LTL мы можем иметь следующие два случая.
        • ж2 ∈ Mшя. По предположению индукции f2 ∈ Mя. Итак, f1 U ж2 ∈ Mя.
        • ж1 ∈ Mшя и е1 U ж2 ∈ Mшя + 1. В силу семантики LTL существует хотя бы один индекс j ≥ i такой, что f2 ∈ Mj. Пусть j 'наименьший из этих индексов. Действуйте, как при доказательстве обратного следствия.

По приведенной теореме Mш1 = M1. Благодаря определению переходов А, f ∈ M1. Следовательно, f ∈ Mш1 и ш f.

Gerth et al. алгоритм

Следующий алгоритм принадлежит Герту, Пеледу, Варди, и Wolper.[3] Также доступен проверенный конструктивный механизм от Schimpf, Merz и Smaus.[5] Предыдущая конструкция заранее создает экспоненциально много состояний, и многие из этих состояний могут быть недоступны. Следующий алгоритм избегает этой предварительной конструкции и состоит из двух этапов. На первом этапе он постепенно создает ориентированный граф. На втором этапе он строит помеченный обобщенный автомат Бюхи (LGBA), определяя узлы графа как состояния и направленные ребра как переходы. Этот алгоритм учитывает достижимость и может производить меньший автомат, но сложность наихудшего случая остается той же.

Узлы графа помечены наборами формул и получаются путем декомпозиции формул в соответствии с их булевой структурой и путем расширения временных операторов, чтобы отделить то, что должно быть истинным немедленно, от того, что должно быть истинным, начиная со следующего состояния. . Например, предположим, что формула LTL f1 U ж2 появляется в метке узла. f1 U ж2 эквивалентно f2 ∨ (f1 ∧ Икс(f1 U ж2Эквивалентное разложение предполагает, что f1 U ж2 верно в одном из следующих двух условий.

  1. ж1 выполняется в текущий момент и (f1 U ж2) выполняется на следующем временном шаге, или
  2. ж2 удерживается на текущем временном шаге

Два случая могут быть закодированы путем создания двух состояний (узлов) автомата, и автомат может недетерминированно перейти к любому из них. В первом случае мы сняли часть бремени доказательства на следующем временном шаге, поэтому мы также создайте другое состояние (узел), которое будет нести обязательство для следующего временного шага в своей метке.

Также необходимо учитывать темпоральный оператор р что может вызвать такой случай split.f1 р ж2 эквивалентно (f1 ∧ f2) ∨ (f2 ∧ Икс(f1 р ж2)) и это эквивалентное разложение предполагает, что f1 р ж2 верно в одном из следующих двух условий.

  1. ж2 выполняется в текущий момент и (f1 р ж2) выполняется на следующем временном шаге, или
  2. (f1 ∧ f2) выполняется на текущем временном шаге.

Чтобы избежать многих случаев в следующем алгоритме, определим функции curr1, следующий1 и curr2 которые кодируют вышеуказанные эквиваленты в следующей таблице.

жcurr1 (f)next1 (f)curr2 (f)
ж1 U ж2{f1}{f1 U ж2 }{f2}
ж1 р ж2{f2}{f1 р ж2 }{f1, f2}
ж1 ∨ f2{f2}∅{f1}

Мы также добавили регистр дизъюнкции в приведенную выше таблицу, так как он также вызывает разделение регистра в автомате.

Ниже приведены два шага алгоритма.

Шаг 1. create_graph

В следующем окне мы представляем первую часть алгоритма построения ориентированного графа. create_graph - функция входа, которая ожидает входную формулу f в нормальная форма отрицания. Вызывает рекурсивную функцию расширять который строит график, заполняя глобальные переменные Узлы, Входящий, Сейчас же, и Следующий.Набор Узлы хранит набор узлов в графе. Карта Входящий отображает каждый узел Узлы к подмножеству Узлы ∪ {init}, который определяет набор входящих ребер. Входящий узла может также содержать специальный символ init, который используется в конечной конструкции автомата для определения набора начальных состояний.Сейчас же и Следующий сопоставить каждый узел Узлы к набору формул LTL. для узла q Сейчас же(q) обозначает набор формул, которым должна удовлетворять остальная часть входного слова, если автомат в настоящее время находится в узле (состоянии) q.Следующий(q) обозначает набор формул, которым должна удовлетворять остальная часть входного слова, если автомат в настоящее время находится в следующем узле (состоянии) после q.

typedefs     LTL: Формулы LTL LTLSet: Наборы формул LTL NodeSet: Наборы узлов графа ∪ {init} глобалы         Узлы : набор узлов графа: = ∅ Входящий: Узлы → NodeSet := ∅         Сейчас же    : Узлы → LTLSet := ∅         Следующий   : Узлы → LTLSet := ∅        функция create_graph(LTL е) {развернуть ({f}, ∅, ∅, {init}) возвращаться (Узлы, Сейчас же, Входящий)      }
 функция расширять(LTLSet curr, LTLSet Старый, LTLSet следующий, NodeSet входящий) {1: если curr = ∅ тогда 2:    если ∃q ∈ Узлы: Следующий(q) = следующий ∧ Сейчас же(q) = старый тогда 3:       Входящий(q): = Входящий(q) ∪ входящие 4: еще 5: q: = new_node() 6:       Узлы := Узлы ∪ {q} 7: Входящий(q): = входящий 8: Сейчас же(q): = старый 9: Следующий(q): = next10: expand (Следующий(q), ∅, ∅, {q}) 11: еще12: f ∈ curr13: curr: = curr  {f} 14: old: = old ∪ {f} 15: матч ж с16:     | истинный, ложный, p или ¬p, где p ∈ AP  →17:       если f = ложный ∨ негр(f) ∈ old тогда18:          пропускать19:       еще20: развернуть (текущее, старое, следующее, входящее) 21: | ж1 ∧ f2 → 22: развернуть (curr ∪ ({f1, f2}  old), old, next, incoming) 23: | Икс g → 24: expand (curr, old, next ∪ {g}, incoming) 25: | ж1 ∨ f2, f1 U ж2, или f1 р ж2 → 26: развернуть (curr ∪ (curr1(е)  старый), старый, следующий ∪ следующий1(f), входящий) 27: expand (curr ∪ (curr2(е)  старый), старый, следующий, входящий) 28: возвращаться }

Кодекс расширять помечены номерами строк для удобства. расширять стремится добавить узел и его последующие узлы в граф. Параметры вызова описывают потенциальный новый узел.

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

В строке 1 если условие проверяет, если curr содержит любую формулу, которую нужно раскрыть. curr пусто, то в строке 2 если condition проверяет, существует ли уже состояние q 'с таким же набором расширенных формул. Если это так, то мы не добавляем избыточный узел, а добавляем параметр входящий в Входящий(q ') в строке 3. В противном случае мы добавляем новый узел q, используя параметры в строках 5–9, и начинаем расширять узел-последователь q, используя следующий(q) в виде нерасширенного набора формул в строке 10.

В случае curr не пусто, тогда у нас есть больше формул для раскрытия и управления переходами со строки 1 на 12. В строках 12–14 формула f из curr выбран и перемещен в Старый. В зависимости от структуры f выполняется остальная часть функции.

  • Если f - литерал, то раскрытие продолжается в строке 20, но если Старый уже содержит негр(f) или f =ложный, тогда Старый содержит противоречивую формулу, и мы отбрасываем этот узел, не делая никакой рекурсии в строке 18.
  • Если f = f1 ∧ f2, то f1 и е2 добавлены к curr и делается рекурсивный вызов для дальнейшего расширения в строке 22.
  • Если f = Икс ж1, то f1 добавлен к следующий для преемника текущего рассматриваемого узла в строке 24.
  • Если f = f1 ∨ f2, f = f1 U ж2, или f = f1 р ж2 затем текущий узел делится на два узла, и для каждого узла выполняется рекурсивный вызов.

Для рекурсивных вызовов curr и следующий изменяются с помощью функций curr1, следующий1, и curr2 которые были определены в приведенной выше таблице.

Шаг 2. Конструирование ЛГБА

Позволять (Узлы, Сейчас же, Входящий) = create_graph (f). Эквивалент LGBA f - А=(Узлы, 2AP, L, Δ, Q0, F), куда

  • L = {(q, a) | q ∈ Узлы и (Сейчас же(д) ∩ AP) ⊆ a ⊆ {p ∈ AP | ¬p ∉ Сейчас же(q)}}
  • Δ = {(q, q ') | q, q '∈ Nodes и q ∈ Incoming (q')}
  • Q0 = {q ∈ Nodes | init ∈ Входящий(q)}
  • Для каждой подформулы g = g1 U грамм2, пусть Fграмм = {q ∈ Nodes | грамм2 ∈ Сейчас же(q) или g ∉ Сейчас же(q)}, то F = {Fграмм | g ∈ cl(f)}

Обратите внимание, что метки узлов в алгоритмической конструкции не содержат отрицания подформул f. В декларативном построении узел имеет набор формул, которые должны быть истинными. Алгоритмическое построение гарантирует правильность без необходимости присутствия всех истинных формул в метке узла.

Инструменты

  • СПОТ LTL2TGBA - Транслятор LTL2TGBA включен в библиотеку проверки объектно-ориентированных моделей SPOT. Доступен онлайн-переводчик.
  • LTL2BA - Быстрый переводчик LTL в BA через чередующиеся автоматы. Доступен онлайн-переводчик.
  • LTL3BA - Актуальное улучшение LTL2BA.

Рекомендации

  1. ^ МОЙ. Варди и П. Вольпер, Рассуждения о бесконечных вычислениях, Информация и вычисления, 115 (1994), 1–37.
  2. ^ Ю. Кестен, З. Манна, Х. Макгуайр, А. Пнуели, Алгоритм принятия решений для полной временной логики высказываний, CAV’93, Элунда, Греция, LNCS 697, Springer – Verlag, 97-109.
  3. ^ а б Р. Герт, Д. Пелед, М.Ю. Варди и П. Вольпер, "Простая автоматическая проверка линейной темпоральной логики на лету", Proc. IFIP / WG6.1 Symp. Спецификация протокола, тестирование и проверка (PSTV95), стр. 3-18, Варшава, Польша, Chapman & Hall, июнь 1995 г.
  4. ^ П. Гастин и Д. Одду, Быстрый перевод LTL в автомат Бюхи, Тринадцатая конференция по компьютерной проверке (CAV '01), номер 2102 в LNCS, Springer-Verlag (2001), стр. 53–65.
  5. ^ А. Шимпф, С. Мерц и Дж. Г. Смаус, "Построение автоматов Bu¨chi для проверки моделей LTL, проверенных в Isabelle / HOL", Proc. Международная конференция по доказательству теорем в логиках высшего порядка (TPHOLs 2009), стр. 424-439, Мюнхен, Германия, Springer, август 2009 г.