Сигнал (проверка модели) - Signal (model checking)

В проверка модели, подполе Информатика, а сигнал или временная последовательность состояний является расширением понятия слов в формальный язык, в котором буквы излучаются непрерывно. В то время как слово традиционно определяется как функция от набора неотрицательных целых чисел до букв, сигнал - это функция от набора действительных чисел до букв. Это позволяет использовать формализм, аналогичный формализму теория автоматов иметь дело с непрерывным сигналом.

пример

Рассмотрим лифт. То, что формально называется письмом, на самом деле может быть такой информацией, как «кто-то нажимает кнопку на 2-м этаже» или «на третьем этаже в настоящее время открыты двери». В этом случае каждый раз сигнал указывает текущее состояние лифта и его кнопок. Затем сигнал может быть проанализирован формальным методом, чтобы проверить, выполняется ли свойство, такое, что «каждый раз, когда лифт вызывается, он прибывает менее чем за три минуты при условии, что никто не удерживал дверь более пятнадцати секунд». Утверждение, подобное этому, обычно выражается в метрическая темпоральная логика, расширение линейная темпоральная логика которые позволяют выразить ограничения по времени.

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

Определение

Учитывая алфавит А, сигнал ${ displaystyle gamma}$ это последовательность ${ displaystyle (I_ {0}, a_ {0}), (I_ {1}, a_ {1}), dots,}$ , конечное или бесконечное, такое что ${ displaystyle a_ {i} in A}$ , каждый ${ Displaystyle I_ {я} substeq mathbb {R} _ {+}}$ - попарно непересекающиеся интервалы, ${ displaystyle 0 in I_ {0}}$ , и ${ displaystyle I_ {i} чашка I_ {i + 1}}$ это тоже интервал. Данный ${ displaystyle t in I_ {i}}$ для некоторых ${ displaystyle i}$ , ${ Displaystyle gamma (т)}$ представляет собой ${ displaystyle a_ {i}}$ .

Свойства

Некоторые авторы ограничивают типы сигналов, которые они рассматривают. Мы перечисляем здесь некоторые стандартные свойства, которым сигнал может удовлетворять, а может и не удовлетворять.

Конечная изменчивость

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

Формально говорят, что сигнал обладает свойством конечной изменчивости, если только последовательность не бесконечна и ${ displaystyle bigcup _ {i} I_ {i}}$ ограничено. Интуитивно, свойство конечной изменчивости утверждает, что не может быть бесконечного числа изменений за конечное время. Обладание свойством конечной изменчивости аналогично понятию не-Зенонова для синхронизированное слово.^[1].

Ограниченная изменчивость

Понятие ограниченной изменчивости - это ограничение на понятие конечной изменчивости. Сигнал имеет свойство ограниченной изменчивости, если существует нижняя граница между началом двух интервалов с одинаковой буквой.^[2]

Прежде чем дать формальное определение, мы дадим пример сигнала, который является конечно переменным, но не ограниченно переменным. Возьми алфавит ${ Displaystyle А = {а, Ь }}$ . Возьмите интервал ${ displaystyle gamma}$ который отправляет вещественные числа формы ${ displaystyle n + { frac {c} {n}}}$ с участием ${ Displaystyle п в mathbb {N}}$ и ${ displaystyle c$ к ${ displaystyle a}$ и все остальные реалы ${ displaystyle b}$ . В течение каждого конечного интервала времени буква меняет конечное количество раз. Таким образом, этот сигнал бесступенчатый. Однако расстояние между двумя последовательными вхождениями буквы ${ displaystyle a}$ произвольно мала. Таким образом, он не обладает свойством ограниченной изменчивости.

Пусть последовательность ${ displaystyle (I_ {0}, a_ {0}), (I_ {1}, a_ {1}), dots}$ . Если ${ Displaystyle а_ {я} neq а_ {я + 1}}$ для каждого целого числа ${ displaystyle i}$ , то говорят, что последовательность обладает свойством ограниченной изменчивости, если существует ${ displaystyle r> 0}$ так что для каждого ${ displaystyle i$ с участием ${ displaystyle a_ {i} = a_ {j}}$ такой, что не существует ${ displaystyle k}$ с участием ${ displaystyle i$ и ${ displaystyle a_ {i} = a_ {k}}$ то разница между нижней границей ${ displaystyle I_ {j}}$ и из ${ displaystyle I_ {i}}$ по крайней мере ${ displaystyle r}$ . Обратите внимание, что каждая последовательность ${ displaystyle gamma}$ эквивалентно последовательности ${ displaystyle gamma '}$ в котором две последовательные буквы различны. Последовательность ${ displaystyle gamma}$ имеет свойство ограниченной изменчивости тогда и только тогда, когда ${ displaystyle gamma '}$ обладает свойством ограниченной изменчивости.

Говорят, что набор сигналов обладает свойством ограниченной изменчивости, если указанная выше нижняя граница ${ displaystyle r}$ можно выбрать одинаковым для каждого сигнала набора.

Мы знаем, что дает основную причину рассматривать сигналы с ограниченной изменчивостью. Предположим, нам нужно создать систему, например сигнальный автомат, которым необходимо вспомнить все, что произошло в последние единицы времени. Если мы знаем, что сигнал ограниченно изменчив, мы можем вычислить верхнюю границу количества действий, имевших место в течение одной единицы времени. Таким образом, мы можем создать такую систему и гарантировать, что для нее потребуется только ограниченная память.

Например, для произвольного предиката ${ displaystyle e}$ , сигнал о том, что утверждение " ${ displaystyle p}$ выполняется когда-нибудь в следующую единицу времени. Имеет свойство ограниченной изменчивости. Действительно, когда это утверждение становится истинным, оно остается истинным для полной единицы времени. Таким образом, разница между двумя случаями, когда это утверждение становится истинным, больше, чем единица времени.

Двудольный сигнал

Сигнал называется двудольный если последовательность интервалов начинается с сингулярного интервала - то есть отрезка, нижняя и верхняя границы которого равны, следовательно, набор является одноэлементным. И если последовательность чередуется между единичными интервалами и открытыми интервалами.

Каждый сигнал эквивалентен двудольному сигналу. В самом деле, любой замкнутый слева интервал является объединением особого интервала и открытого слева интервала в этом порядке. То же самое и для закрытых справа интервалов.

А сигнальный автомат чтение двудольного сигнала имеет особую форму. Его набор местоположений может быть разделен на местоположения для единственного интервала и местоположения для открытых интервалов. Каждый переход идет от единственного места к открытому и взаимно.

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

Синхронизированное слово

использованная литература

^ Брихай, Томас; Geeraerts, Gilles; Хо, Си-Мин; Монмеж, Бенджамин (2017). «Автоматизированная по времени проверка MITL по сигналам». Международный симпозиум по временному представлению и рассуждению: 4.
^ Никович, Деян (2008). «3». Проверка временных и гибридных свойств: теория и приложения (Тезис). п. 45.

Кини, Дилип Рагхунатх; Кришна, Шанкара Нараянан; Пандья, Паритош К. (2011). «О построении автоматов сигналов безопасности для MITL [U, S] с использованием временных проекций». Форматы: 227.

[FiniteVariability-1] Брихай, Томас; Geeraerts, Gilles; Хо, Си-Мин; Монмеж, Бенджамин (2017). «Автоматизированная по времени проверка MITL по сигналам». Международный симпозиум по временному представлению и рассуждению: 4.

[Bounded-2] Никович, Деян (2008). «3». Проверка временных и гибридных свойств: теория и приложения (Тезис). п. 45.

[1]

[2]