Для чего нужны решетки?

Question

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

С тех пор я нашел бесплатную бумагу Заказанные наборы и полные решетки: учебник для компьютерных наук, для других заинтересованных читателей.

Answer 5

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

Answer 6

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