Применение метрических структур на позах / решетках в теории CS

17

Поскольку термин перегружен, сначала дается краткое определение. Poset - это множество наделенное частичным порядком . Для двух элементов , мы можем определить (join) как их наименьшую верхнюю границу в и аналогично определить (meet) (join) как наибольшую нижнюю границу. $X$ $\le$ $a,b \in X$ $x \vee y$ $X$ $x \wedge y$

Решетка - это набор, в котором любые два элемента имеют уникальную встречу и уникальное соединение.

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

Но меня интересуют приложения, которые используют метрические структуры на решетках. Простой пример исходит из кластеризации, где любая антимонотонная субмодульная функция (антимонотон означает, что если ) индуцирует метрику $f : X \rightarrow R$ $x \le y, f(x) \le f(y)$

d (Икс, Y) знак равно 2 е (Икс \land Y) - е (Икс) - е (Y)

$d(x,y) = 2f(x \wedge y) - f(x) - f(y)$

Этот показатель широко использовался для сравнения двух разных кластеров набора данных.

Существуют ли другие применения решеток, которые заботятся о метрических структурах? Я интересовался приложением теории предметной области / статического анализа, но пока не видел необходимости в метриках .

reference-request co.combinatorics metrics lattice order-theory Суреш Венкат
источник

12

Сначала комментарий. Ваш вопрос в некотором роде зависит от того, насколько геометрически вы намереваетесь обозначить слово «метрика». Разумно использовать ультраметрики в семантике и статическом анализе, но ультраметрики имеют скорее комбинаторную, чем геометрическую интерпретацию. (Это вариант наблюдения, что теория области имеет вид комбинаторного, а не геометрического использования топологии.)

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

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

$\Omega$ $\mathbb{N}$ $2^{-n}$ $n$

$p : \Omega \to \Omega$ $n+1$ $n$ $\top = \mathbb{N}$

Нил Кришнасвами
источник

ах интересно. Отвечая на ваш вопрос, все, что меня волнует, это то, что метрика просто так: она удовлетворяет неравенству треугольника. Так что ультраметрика в порядке. Однако (и это мой недостаток в этом вопросе) мне кажется, что использование метрики здесь структурно, чтобы получить доступ к Банаху. Вы не заботитесь о метрике как таковой (и поэтому такие вещи, как аппроксимация метрики или ее вычисление не имеют значения). Это правильно ?

Суреш Венкат

4

Да, мы не очень заботимся о метрике. Это на самом деле источник дискомфорта с метрическими или пошаговыми моделями - почему мы отслеживаем информацию, которая нас не волнует? Показ того, что модель стабильна в классе приближений к метрике (возможно, консервативна в отношении сжимаемости), фактически повысит комфорт с ней.

Нил Кришнасвами

9

В качестве альтернативы наиболее часто используемым CPO, Арнольд и Ниват исследовали (полные) метрические пространства как области денотационной семантики [1]. В своей диссертации Бонсанге [2] исследовал двойственность между такой денотационной семантикой и аксиоматической семантикой. Я упоминаю это здесь, потому что это дает очень полную общую картину.

[1]: Арнольд, М. Ниват: Метрические интерпретации бесконечных деревьев и семантика недетерминированных рекурсивных программ. Теор. Вычи. Sci. 11: 181-205 (1980).
[2]: М. М. Бонсанге Топологическая двойственность в семантике том 8 ENTCS, Elsevier 1998.

Кай
источник

Фантастика - я не знал, что этот тезис был онлайн!

Нил Кришнасвами

3

Я дал понять Марчелло (Бонсанге), что о нем говорят. (Возможно, он присоединится.)

Дейв Кларк

5

Вот один из них (по совпадению, сверху моей очереди на чтение):

Сварат Чаудхури, Сумит Гулвани и Роберто Люблинерман. Анализ непрерывности программ. POPL 2010.

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

Я еще не видел ничего, что требовало бы метрического пространства - кажется, что это можно было бы сделать с использованием общей топологии - но я только на странице 3. :)

Нил Торонто
источник

1

Конечно, здесь нет никаких поцелов или решеток, как в предыдущем ответе. вот чего мне не хватает

Суреш Венкат

3

Извиняюсь за добавление другого ответа, но этот не связан с моим другим выше.

Метрические пространства, которые я обычно использую, чтобы раздражать (или это воспитывает?) Студентов параллелизма, это бесконечные следы. Индуцируемая им топология - именно та, которую Алперн и Шнайдер [1] использовали для характеристики безопасности и живучести как предельно замкнутых и плотных соответственно.

\begin{array}{rcl} d : Σ^{ω} \times Σ^{ω} & ⟶ & р_{\geq 0} \\ (σ, τ) & \mapsto & 2^{- вир {я \in N | σ |_{я} знак равно τ |_{я}}} \end{array}

$\begin{array}{@{}rcl} d : \Sigma^\omega\times\Sigma^\omega & \longrightarrow & \mathbb{R}_{{}\ge 0}\\ % (\sigma,\tau) & \mapsto & 2^{-\sup \{~i\in\mathbb{N} ~|~ \sigma|_i = \tau|_i~\}} \end{array}$

σ |_{i}

$\sigma|_i$

σ

$\sigma$

i

$i$

2^{- \infty} = 0

$2^{-\infty} = 0$

Оглядываясь назад, я понимаю, что в этом ответе также отсутствует основной компонент структуры решетки или осетры. Такая структура решетки, тем не менее, присутствует при перемещении на один уровень до того, что Кларксон и Шнайдер называют гиперсвойством [2]. На момент написания статьи мне непонятно, как поднять метрику.

[1] B Alpern и FB Schneider. Определение жизненности. IPL, 21 (4): 181–185, 1985.
[2] М. Р. Кларксон и Ф. Б. Шнайдер. Hyperproperties. CSF, p51-65, IEEE, 2008.

Кай
источник

\sum_{k = 1}^{n} k = n (n + 1) / 2

$\sum_{k=1}^n k = {n(n+1)}/{2}$

@ HCH спасибо, я соответствующим образом отредактировал свой пост и удалил вопиющий крик за советы по форматированию.

Кай

Хорошая формула!

Сянь-Чи Чанг 之之

Применение метрических структур на позах / решетках в теории CS

Ответы: