Временная логика переменного времени

В информатике , темпоральная логика переменного времени , или ATL с ветвящимся временем , представляет собой темпоральную логику которая расширяет логику дерева вычислений (CTL) для нескольких игроков. ^[1] ATL естественным образом описывает вычисления многоагентных систем и параллельных игр . ^[2] Количественная оценка в ATL осуществляется по программным путям, которые являются возможными результатами игр. ^[3] ATL использует формулы переменного времени для построения средств проверки моделей с целью решения таких проблем, как восприимчивость, реализуемость и управляемость.

Примеры

В ATL можно писать логические формулы, например $\langle \langle \{a,b\}\rangle \rangle Fp$ это выражает тот факт, что у агентов a и b есть стратегия, обеспечивающая сохранение свойства p в будущем, что бы ни делали другие агенты системы.

Расширения и варианты

ATL* является расширением ATL, поскольку CTL* расширяет CTL. ATL* позволяет писать более сложные временные цели, например $\langle \langle \{a,b\}\rangle \rangle (Fp\land Gq)$ . Белардинелли и др. предлагает вариант ATL на конечных трассах. ^[4] ATL был расширен контекстом для хранения текущих стратегий, используемых агентами. ATL* расширяется за счет логики стратегии.

ATL был обобщен и включает эпистемические особенности. В 2003 году Ван дер Хук и Вудридж предложили ATEL: логику ATL, дополненную эпистемическим оператором из эпистемической логики . ^[5] В 2004 году Пьер-Ив Шоббенс предложил варианты ATL с несовершенным запоминанием. ^[6]

В ATL невозможно выразить свойства отдельных целей. Вот почему в 2010 году Чаттерджи , Хенцингер и Питерман представили стратегическую логику, логику первого порядка , в которой стратегии являются гражданами первого порядка. ^[7] Логика стратегии включает в себя как ATL, так и ATL*.

См. также

Линейная темпоральная логика

Ссылки

^ Алур, Раджив ; Хенцингер, Томас А .; Купферман, Орна (1997). «Темпоральная логика переменного времени». Материалы 38-го ежегодного симпозиума по основам информатики . Компьютерное общество IEEE. стр. 100–109. дои : 10.1109/SFCS.1997.646098 . ISBN 0-8186-8197-7 .
^ ван Дриммелен, Говерт (2003). «Выполнимость во временной логике переменного времени». Материалы 18-го ежегодного симпозиума IEEE по логике в информатике . Компьютерное общество IEEE. дои : 10.1109/LICS.2003.1210060 . ISBN 0-7695-1884-2 .
^ Алур, Раджив; Хензингер, Томас А.; Купферман, Орна (2002). «Темпоральная логика переменного времени» . Журнал АКМ . 49 (5): 672–713. дои : 10.1145/585265.585270 . S2CID 15984608 .
^ Белардинелли, Франческо; Ломушио, Алессио; Мурано, Аньелло; Рубин, Саша (2018). «Темпоральная логика переменного времени на конечных следах» : 77–83. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ ван дер Хук, Вибе; Вулдридж, Майкл (1 октября 2003 г.). «Сотрудничество, знание и время: временная эпистемическая логика чередующегося времени и ее приложения». Студия Логика . 75 (1): 125–157. дои : 10.1023/А:1026185103185 . ISSN 1572-8730 . S2CID 10913405 .
^ Шоббенс, Пьер-Ив (1 апреля 2004 г.). «Логика переменного времени с несовершенным отзывом» . Электронные заметки по теоретической информатике . LCMAS 2003, Логика и коммуникация в многоагентных системах. 85 (2): 82–93. дои : 10.1016/S1571-0661(05)82604-0 . ISSN 1571-0661 .
^ Чаттерджи, Кришненду ; Хензингер, Томас А.; Питерман, Нир (01.06.2010). «Логика стратегии» (PDF) . Информация и вычисления . Специальный выпуск: 18-я Международная конференция по теории параллелизма (CONCUR 2007). 208 (6): 677–693. дои : 10.1016/j.ic.2009.07.004 . ISSN 0890-5401 .

[1] Алур, Раджив ; Хенцингер, Томас А .; Купферман, Орна (1997). «Темпоральная логика переменного времени». Материалы 38-го ежегодного симпозиума по основам информатики . Компьютерное общество IEEE. стр. 100–109. дои : 10.1109/SFCS.1997.646098 . ISBN 0-8186-8197-7 .

[2] ван Дриммелен, Говерт (2003). «Выполнимость во временной логике переменного времени». Материалы 18-го ежегодного симпозиума IEEE по логике в информатике . Компьютерное общество IEEE. дои : 10.1109/LICS.2003.1210060 . ISBN 0-7695-1884-2 .

[3] Алур, Раджив; Хензингер, Томас А.; Купферман, Орна (2002). «Темпоральная логика переменного времени» . Журнал АКМ . 49 (5): 672–713. дои : 10.1145/585265.585270 . S2CID 15984608 .

[4] Белардинелли, Франческо; Ломушио, Алессио; Мурано, Аньелло; Рубин, Саша (2018). «Темпоральная логика переменного времени на конечных следах» : 77–83. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[5] ван дер Хук, Вибе; Вулдридж, Майкл (1 октября 2003 г.). «Сотрудничество, знание и время: временная эпистемическая логика чередующегося времени и ее приложения». Студия Логика . 75 (1): 125–157. дои : 10.1023/А:1026185103185 . ISSN 1572-8730 . S2CID 10913405 .

[6] Шоббенс, Пьер-Ив (1 апреля 2004 г.). «Логика переменного времени с несовершенным отзывом» . Электронные заметки по теоретической информатике . LCMAS 2003, Логика и коммуникация в многоагентных системах. 85 (2): 82–93. дои : 10.1016/S1571-0661(05)82604-0 . ISSN 1571-0661 .

[7] Чаттерджи, Кришненду ; Хензингер, Томас А.; Питерман, Нир (01.06.2010). «Логика стратегии» (PDF) . Информация и вычисления . Специальный выпуск: 18-я Международная конференция по теории параллелизма (CONCUR 2007). 208 (6): 677–693. дои : 10.1016/j.ic.2009.07.004 . ISSN 0890-5401 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]