Часы (проверка модели) - Clock (model checking)

В проверка модели, подполе Информатика, а Часы математический объект, используемый для моделирования времени. Точнее, часы измеряют, сколько времени прошло с тех пор, как произошло определенное событие, в этом смысле часы являются более точной абстракцией секундомер. В модели некоторой конкретной программы значение часов может быть либо временем с момента запуска программы, либо временем, прошедшим с того момента, как в программе произошло определенное событие. Эти часы используются в определении синхронизированный автомат, сигнальный автомат, временная пропозициональная темпоральная логика и временная логика часов. Они также используются в таких программах, как UPPAAL которые реализуют синхронизированные автоматы.^[1]

Как правило, в модели системы используется много часов. Эти несколько часов необходимы для отслеживания ограниченного количества событий. Все эти часы синхронизированы. Это означает, что разница в значениях между двумя фиксированными часами остается постоянной, пока один из них не будет перезапущен. На языке электроники это означает, что часы дрожь нулевой.

Пример

Допустим, мы хотим смоделировать лифт в десятиэтажном здании. Наша модель может иметь ${ displaystyle n}$ часы ${ displaystyle c_ {0}, dots, c_ {9}}$ , так что значение часов ${ displaystyle c_ {i}}$ это время, когда кто-то ждал лифта на этаже ${ displaystyle i}$ . Эти часы запускаются, когда кто-то вызывает лифт на этаже ${ displaystyle i}$ (и лифт на этом этаже еще не вызывали с момента последнего посещения этого этажа). Эти часы можно выключить, когда лифт поднимется на этаж. ${ displaystyle i}$ . В этом примере нам действительно нужно десять разных часов, потому что нам нужно отслеживать десять независимых событий. Еще часы ${ displaystyle s}$ может использоваться для проверки того, сколько времени лифт провел на определенном этаже.

Затем модель этого лифта может использовать эти часы для подтверждения того, удовлетворяет ли программа лифта таким свойствам, как «если предположить, что лифт не удерживается на этаже более пятнадцати секунд, тогда никто не должен ждать лифт более трех минут. ". Чтобы проверить, выполняется ли это утверждение, достаточно проверить, что при каждом запуске модели, в которой часы ${ displaystyle s}$ всегда меньше пятнадцати секунд, каждые часы ${ displaystyle c_ {i}}$ выключается до истечения трех минут.

Определение

Формально набор ${ displaystyle X}$ часов - это просто конечный набор^[1]^:191. Каждый элемент набора часов называется часами. Интуитивно часы похожи на переменную в логика первого порядка, это элемент, который можно использовать в логической формуле и который может принимать несколько разных значений.

Оценка часов

А оценка часов или же интерпретация часов^[1]^:193 ${ displaystyle nu}$ над ${ displaystyle X = {x_ {1}, dots, x_ {n} }}$ обычно определяется как функция от ${ displaystyle X}$ к множеству неотрицательных вещественных. Точно так же оценка может рассматриваться как точка в ${ Displaystyle mathbb {R} _ { geq 0} ^ {п}}$ .

В первоначальное назначение ${ displaystyle nu _ {0}}$ - это постоянная функция, отправляющая каждые часы в 0. Интуитивно она представляет начальное время программы, когда все часы инициализируются одновременно.

Учитывая назначение часов ${ displaystyle nu}$ , и настоящий ${ Displaystyle т geq 0}$ , ${ displaystyle nu + t}$ обозначает назначение часов, отправляющих каждые часы ${ displaystyle x in C}$ к ${ Displaystyle ню (х) + т}$ . Интуитивно он представляет собой оценку ${ displaystyle nu}$ после которого ${ displaystyle t}$ единицы времени прошли.

Учитывая подмножество ${ displaystyle r substeq C}$ часов, ${ displaystyle nu [г rightarrow 0]}$ обозначает присвоение, подобное ${ displaystyle nu}$ в котором часы ${ displaystyle r}$ сброшены. Формально, ${ displaystyle nu [г rightarrow 0]}$ отправляет каждые часы ${ displaystyle x in r}$ до 0 и каждые часы ${ Displaystyle х не в г}$ к ${ Displaystyle ню (х)}$ .

Неактивные часы

Программа UPPAAL ввести понятие неактивные часы.^[2] Часы неактивны в какое-то время, если нет возможности в будущем, в которой значение часов проверяется без предварительного сброса. В нашем примере выше часы ${ displaystyle c_ {i}}$ считается неактивным, когда лифт поднимается на этаж ${ displaystyle i}$ , и остается неактивным, пока кто-нибудь не вызовет лифт на этаже ${ displaystyle i}$ .

При разрешении неактивных часов оценка может связывать часы ${ displaystyle x}$ с особой ценностью ${ displaystyle bot}$ чтобы указать, что он неактивен. Если ${ Displaystyle ню (х) = бот}$ тогда ${ Displaystyle ( ню + т) (х)}$ также равно ${ displaystyle bot}$ .

Ограничение часов

An ограничение атомных часов это просто термин формы ${ displaystyle x sim c}$ , куда ${ displaystyle x}$ это часы, ${ displaystyle sim}$ является оператором сравнения, например <, ≤, = ≥ или>, и ${ displaystyle c in mathbb {N}}$ - интегральная постоянная. В нашем предыдущем примере мы можем использовать ограничения атомных часов ${ displaystyle c_ {i} leq 180}$ заявить, что человек на этаже ${ displaystyle i}$ ждал меньше трех минут и ${ displaystyle s> 15}$ заявить, что лифт оставался на каком-то этаже более пятнадцати секунд. Оценка ${ displaystyle nu}$ удовлетворяет оценке атомных часов ${ displaystyle x sim c}$ если и только если ${ Displaystyle ню (х) сим с}$ .

А ограничение часов является либо конечным соединение ограничения атомных часов или константа "истина" (которую можно рассматривать как пустую конъюнкцию). Оценка ${ displaystyle nu}$ удовлетворяет ограничение по времени ${ displaystyle bigwedge _ {я = 1} ^ {n} x_ {i} sim _ {i} c_ {i}}$ если он удовлетворяет каждому ограничению атомных часов ${ displaystyle x_ {i} sim _ {i} c_ {i}}$ .

Диагональное ограничение

В зависимости от контекста ограничение атомных часов также может иметь вид ${ displaystyle x_ {i} sim x_ {j} + c}$ . Такое ограничение называется диагональным ограничением, потому что ${ displaystyle x_ {1} = x_ {2} + c}$ определяет диагональную линию в ${ Displaystyle mathbb {R} _ { geq 0} ^ {2}}$ .

Разрешение диагональных ограничений может позволить уменьшить размер формулы или автомата, используемого для описания системы. Однако сложность алгоритма может возрасти, если разрешены диагональные ограничения. В большинстве систем, использующих часы, разрешение диагонального ограничения не увеличивает выразительность логики. Теперь мы объясним, как кодировать такое ограничение с помощью логической переменной и недиагонального ограничения.

Диагональное ограничение ${ displaystyle x_ {i} sim x_ {j} + c}$ можно смоделировать с использованием недиагонального ограничения следующим образом. Когда ${ displaystyle x_ {j}}$ сброшен, проверьте ${ displaystyle x_ {i} sim c}$ держит или нет. Напомним эту информацию в логической переменной ${ displaystyle b_ {я, j, c}}$ и заменить ${ displaystyle x_ {i} sim x_ {j} + c}$ по этой переменной. Когда ${ displaystyle x_ {i}}$ сброшен, установлен ${ displaystyle b_ {я, j, c}}$ к истине, если ${ displaystyle sim}$ <или ≤ или если ${ displaystyle sim}$ is = и ${ displaystyle c = 0}$ .

Способ кодирования логической переменной зависит от системы, которая использует часы. Например, UPPAAL поддерживает логические переменные напрямую. Временные автоматы и сигнальные автоматы могут закодировать логическое значение в своих местах. В временная логика часов через синхронизированные слова логическая переменная может быть закодирована с использованием новых часов ${ displaystyle x_ {я, j, c}}$ , значение которого равно 0 тогда и только тогда, когда ${ displaystyle b_ {я, j, c}}$ ложно. То есть, ${ displaystyle x_ {я, j, c}}$ сбрасывается, пока ${ displaystyle x_ {я, j, c}}$ предполагается ложным. В временная пропозициональная темпоральная логика, формула ${ displaystyle x_ {i}. phi}$ , который перезапускается ${ displaystyle x_ {i}}$ а затем оценивает ${ displaystyle phi}$ , можно заменить формулой ${ displaystyle x_ {i}. ((x_ {i} sim x_ {j} + c подразумевает phi _ { top}) land ( neg x_ {i} sim x_ {j} + c подразумевает phi bot))}$ , куда ${ displaystyle phi _ { top}}$ и ${ displaystyle phi _ { bot}}$ копии формул ${ displaystyle phi}$ , куда ${ displaystyle x_ {i} sim x_ {j} + c}$ заменяются константами true и false соответственно.

Наборы, определяемые ограничениями часов

Ограничение времени определяет набор оценок. В литературе рассматриваются два вида таких наборов.

А зона - непустой набор оценок, удовлетворяющий ограничению времени. Зоны и ограничения часов реализованы с использованием матрица границ разностей.

Учитывая модель ${ displaystyle M}$ , он использует конечное число констант в своих ограничениях времени. Позволять ${ displaystyle K}$ быть самой большой используемой постоянной. А область, край - это непустая зона, в которой нет ограничений больше, чем ${ displaystyle K}$ используются, причем такие, что он минимален для включения.

Смотрите также

Примечания

^ ^а ^б ^c Алур, Раджив; Дилл, Дэвид Л. (25 апреля 1994 г.). «Теория временных автоматов» (PDF). Теоретическая информатика. 126 (2): 183–235. Дои:10.1016/0304-3975(94)90010-8.
^ Берманн, Герд; Дэвид, Александр; Ларсен, Ким Джи (28 ноября 2006 г.). "Учебник по Уппал 4.0" (PDF): 28. Цитировать журнал требует | журнал = (помощь)

[AlurDill-1] а ^б ^c Алур, Раджив; Дилл, Дэвид Л. (25 апреля 1994 г.). «Теория временных автоматов» (PDF). Теоретическая информатика. 126 (2): 183–235. Дои:10.1016/0304-3975(94)90010-8.

[2] Берманн, Герд; Дэвид, Александр; Ларсен, Ким Джи (28 ноября 2006 г.). "Учебник по Уппал 4.0" (PDF): 28. Цитировать журнал требует | журнал = (помощь)

[1]

[2]