stringtranslate.com

Обоснованная семантика

В информатике обоснованная семантика — это трехзначная семантика логического программирования , которая дает точное значение общим логическим программам.

История

Обоснованная семантика была определена Ван Гелдером и др. в 1988 году. [ 1] [2] Система Prolog XSB реализует обоснованную семантику с 1997 года. [3] [4]

Трехзначная логика

Обоснованная семантика назначает уникальную модель каждой общей логической программе. Однако вместо того, чтобы назначать только истинные или ложные предложения , она добавляет третье неизвестное значение для представления невежества. [1]

Простым примером является логическая программа, которая кодирует два предложения aи b, причем , a должно быть истинным, когда bне является , и наоборот:

а  :-  не ( б ). б  :-  не ( а ).

ни то, aни другое не bявляются истинными или ложными, но оба имеют неизвестное значение истинности. В двузначной стабильной семантике модели есть две стабильные модели, одна из которых aистинна и bложна, а другая bистинна и aложна.

Программы стратифицированной логики имеют 2-значную хорошо обоснованную модель, в которой каждое предложение либо истинно, либо ложно. Это совпадает с уникальной стабильной моделью программы. Хорошо обоснованную семантику можно рассматривать как трехзначную версию стабильной семантики модели . [5]

Сложность

В 1989 году Ван Гелдер предложил алгоритм для вычисления обоснованной семантики программы пропозициональной логики, временная сложность которой квадратична по размеру программы. [6] По состоянию на 2001 год не было известно общего субквадратичного алгоритма для этой задачи. [7]

Ссылки

  1. ^ ab Ван Гелдер, Аллен; Росс, Кеннет А.; Шлипф, Джон С. (июль 1991 г.). «Хорошо обоснованная семантика для общих логических программ». Журнал ACM . 38 (3): 619–649. doi :10.1145/116825.116838. ISSN  0004-5411.
  2. ^ Ван Гелдер, Аллен; Росс, Кеннет; Шлипф, Джон С. (1988). «Необоснованные множества и обоснованная семантика для общих логических программ». Труды седьмого симпозиума ACM SIGACT-SIGMOD-SIGART по принципам систем баз данных . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 221–230. doi : 10.1145/308386.308444 . ISBN 0897912632.
  3. ^ Кернер, Филипп; Леушель, Майкл; Барбоза, Жуан; Коста, Витор Сантос; Даль, Вероника; Эрменегильдо, Мануэль В.; Моралес, Хосе Ф.; Вилемакер, Ян; Диас, Дэниел; Абреу, Сальвадор; Чатто, Джованни (ноябрь 2022 г.). «Пятьдесят лет Пролога и не только». Теория и практика логического программирования . 22 (6): 776–858. дои : 10.1017/S1471068422000102 . hdl : 10174/33387 . ISSN  1471-0684.
  4. ^ Рао, Прасад; Сагонас, Константинос; Свифт, Терренс; Уоррен, Дэвид С.; Фрейре, Джулиана (1997), Дикс, Юрген; Фурбах, Ульрих; Нероде, Анил (ред.), "XSB: система для эффективного вычисления обоснованной семантики", Логическое программирование и немонотонные рассуждения , т. 1265, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 430–440, doi :10.1007/3-540-63255-7_33, ISBN 978-3-540-63255-9, получено 2023-11-17
  5. ^ Пржимусинский, Теодор. Хорошо обоснованная семантика совпадает с трехзначной стабильной семантикой . Fundamenta Informaticae XIII стр. 445-463, 1990.
  6. ^ Ван Гелдер, А. (1989). Чередующаяся фиксированная точка логических программ с отрицанием. Труды восьмого симпозиума ACM SIGACT-SIGMOD-SIGART по принципам систем баз данных. ACM Press. стр. 1–10. doi : 10.1145/73721.73722 . ISBN 978-0-89791-308-9.
  7. ^ Лонк, Збигнев; Трушчинский, Мирослав (2001). «О проблеме вычисления обоснованной семантики». Теория и практика логического программирования . 1 (5): 591–609. arXiv : cs/0101014 . doi :10.1017/S1471068401001053. ISSN  1471-0684.