Для чего используются решетки?

15

Википедия говорит :

Полные решетки появляются во многих приложениях в математике и информатике

Это просто ссылка на тот факт, что стандартная булева алгебра, используемая в вычислениях, является полной решеткой? Есть ли что-то, что мы приобретаем, работая на абстрактном уровне решеток, а не конкретно с булевой логикой?

Поиск по Google не находит много по теме, но я, вероятно, использую неправильные ключевые слова.

Xodarap
источник
en.wikipedia.org/wiki/Intuitionistic_logic и другие неклассические логики используют различные виды полных решеток для своей семантики.
Андрас Саламон

Ответы:

11

Смотрите, например, эту книгу: Теория решеток с приложениями, Виджей К. Гарг , которая начинается следующим образом:

Частичный порядок и теория решеток в настоящее время играют важную роль во многих дисциплинах информатики и техники. Например, у них есть приложения в распределенных вычислениях (векторные часы, глобальное обнаружение предикатов), теории параллелизма (pomsets, вхождения сетей), семантики языка программирования (семантика с фиксированной точкой) и интеллектуального анализа данных (анализ концепции). Они также полезны в других дисциплинах математики, таких как комбинаторика, теория чисел и теория групп. В этой книге я представлю важные результаты в теории частичного порядка вместе с их приложениями в информатике. Предвзятость книги касается вычислительных аспектов теории решеток (алгоритмы) и приложений (особенно распределенных систем).

В книге не упоминается теория рекурсии (теория вычислимых множеств), но из статьи Википедии по теории вычислимости мы видим:

Когда Пост определил понятие простого множества как множество с бесконечным дополнением, не содержащее никакого бесконечного множества, он начал изучать структуру рекурсивно перечислимых множеств при включении. Эта решетка стала хорошо изученной структурой. Рекурсивные наборы могут быть определены в этой структуре с помощью основного результата, что набор является рекурсивным тогда и только тогда, когда набор и его дополнение являются рекурсивно перечислимыми. Бесконечные множества имеют всегда бесконечные рекурсивные множества; но с другой стороны, простые наборы существуют, но не имеют коинфинитного рекурсивного надмножества. Пост (1944) представил уже гиперпростые и гиперпростые множества; были построены более поздние максимальные множества, которые являются повторными, так что каждый повторный набор является либо конечным вариантом данного максимального набора, либо является ко-конечным. Почта' Первоначальной мотивацией при исследовании этой решетки было найти такое структурное понятие, что каждое множество, удовлетворяющее этому свойству, не находится ни в степени Тьюринга рекурсивных множеств, ни в степени Тьюринга проблемы остановки. Пост не нашел такого свойства, и вместо решения его проблемы использовались приоритетные методы; Харрингтон и Соаре (1991) нашли в конечном итоге такую ​​собственность.

Дальнейшее чтение смотрите в блоге « Теория решеток» для программистов и не-компьютерщиков .

Пол Г.Д.
источник
2
Позвольте мне добавить к этому, что решетки и связанное с ними понятие предметной области широко используются в семантике языков программирования.
Андрей Бауэр
@AndrejBauer не могли бы вы дать некоторые примеры для примеров? Благодарю.
AMC
3

Ссылки, данные Полем Г.Д., действительно очень уместны. Итак, давайте сосредоточимся на второстепенной проблеме в этом ответе. Некоторое время назад я немного читал о решетках и начал задумываться о том, не было бы понятие полурешетки более подходящим для приложений. Вы могли бы возразить, что полная полурешетка автоматически также является решеткой, но гомоморфизмы и подструктуры (то есть подрешетки и субрешетки) различны.

Я впервые столкнулся с (полу) решетками при изучении полугрупп, как коммутативные идемпотентные полугруппы. Затем я подумал о связи между иерархическими структурами и решетками и заметил, что дерево, естественно, также является полурешеткой. Затем я нашел решетки в контексте безопасности и в программном анализе, и мне всегда казалось, что структура полурешетки была действительно важной частью, и решетка была просто взята, потому что ее можно было получить «бесплатно». Даже для алгебры Гейтинга существует асимметрия между конъюнкцией и дизъюнкцией, что наводит меня на мысль о том, что модель асимметричной полурешетки может дать больше понимания, чем модель симметричной решетки.

Томас Климпел
источник
1
Можете ли вы рассказать, как деревья являются полурешетками? И особенно если есть какие-то интересные теоремы, которые мы можем доказать о структурах данных, используя (полу) решетки?
Xodarap
@Xodarap Если мы рассматриваем дерево как частично упорядоченный набор, объединение двух узлов дается их наименьшим общим предком. Что касается вашего запроса о структурах данных, я думаю, это связано с моим предыдущим вопросом о структуре данных для полурешеток . В то время я пришел к выводу, что это удивительно нетривиальная проблема. Кроме того, я не собирался слишком далеко уходить от мейнстрима, поэтому я был очень рад найти этот пост с отличным справочным разделом.
Томас Климпел
3

очень важный, но не очень известный случай - он хорошо известен среди теоретиков, но не так хорошо известен в смысле обучения студентов - использование решетки для доказательства суперполиномиальных нижних оценок размера монотонных цепей Вычислительная клика, за которую Разборов получил Неванлиннскую премию . однако оригинальная конструкция очень техническая, и более поздние конструкции, например, Берг / Ульфберг, упрощают каркас без ссылки на решетки.

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

так что да, решетки могут рассматриваться как более экзотический математический объект [Разборов говорил в другом месте о своем стиле применения продвинутой математики к CS], который может соответствовать некоторому другому более «конкретному» объекту в CS, в данном случае это «врата приближения» т. е. логические элементы в схемах, которые дают «приблизительно правильные» ответы и решетка которых является своего рода «индукционной структурой» для преобразования точной схемы в неточную, приблизительную схему.

ВЗН
источник
2

Регулярные метки ребер и связанные с ними структуры образуют распределительную решетку (см., Например, здесь ). Это может быть использовано для эффективного поиска в пространстве всех регулярных меток ребер для данного графа (см. Здесь ). В качестве приложения вы можете определить, можно ли нарисовать карту в виде картограммы с определенным назначением области для граней.

A.Schulz
источник
2

Также удивительно (для меня, по крайней мере) криптография . Проверьте это, это позволяет новые атаки известных криптосистем и дает надежду на постквантово-вычислительную криптографию.

Helios
источник
2
Такая «периодическая» решетка не та, о которой спрашивает ОП. Речь идет о структурах с бинарными операциями встречи и соединения.
Андрас Саламон
К сожалению. Тогда я не понял, о чем спрашивал ОП.
Гелиос
Но решетки, о которых говорит Гелиос, на самом деле являются распределительными решетками в обычном порядке доминирования. Кроме того, и я могу ошибаться, но я думаю, что любая распределительная решетка может быть встроена в пространство как подмножество периодической решетки. И они, пожалуй, самая захватывающая вещь в криптографии сейчас.
Сашо Николов