Обоснованная семантика - Well-founded semantics

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

История

Обоснованная семантика была определена Van Gelder et al. в статье 1991 года.[1]

Отношения к другим моделям

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

Например, если мы знаем, что

Образец А - моль, если образец А не летает днем.

но мы не знаем, был ли образец А летает днем, хорошо обоснованная семантика присвоила бы предложению `` образец A - моль '' значение Нижний что ни истинный ни ложный.

Приложения

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

Сложность и алгоритмы

Самый быстрый из известных алгоритмов вычисления WF-семантики в целом имеет квадратичную сложность.[нужна цитата ]

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

  1. ^ А. Ван Гельдер, К.А. Росс и Дж. Schlipf. Обоснованная семантика для общих логических программ. Журнал ACM 38 (3) стр. 620–650, 1991
  2. ^ Пржимусинский, Теодор. Хорошо обоснованная семантика совпадает с трехзначной стабильной семантикой. Fundamenta Informaticae XIII стр. 445-463, 1990.