Что такое коиндукция?

cs.stackexchange https://cs.stackexchange.com/questions/525

Вопрос

Я слышал о (структурной) индукции. Это позволяет вам создавать конечные структуры из более мелких и дает вам принципы доказательства рассуждения о таких структурах. Идея достаточно ясна.

Но как насчет коиндукции? Как это работает? Как можно сказать что -то убедительное в отношении бесконечной структуры?

Существует (по крайней мере) два угла для решения, а именно: коиндукция как способ определения вещей и как техника доказательства.

Относительно коиндукции в качестве техники доказательства, какова связь между коиндукцией и бизимуляцией?

Это было полезно?

Решение

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

  • языки (наборы строк над некоторым алфавитом, которые могут быть конечными);
  • Языки деревьев (наборы деревьев над некоторым алфавитом);
  • следы выполнения нетерминистской системы;
  • вещественные числа;
  • наборы целых чисел;
  • наборы функций от целых чисел до целых чисел; …

Соингукированность как самая большая точка фиксации

В тех случаях, когда индуктивные определения строят структуру из элементарных строительных блоков, коинтиктивные определения формируют структуры из того, как их можно деконструировать. Например, тип списков, элементы которых находятся в наборе A определяется следующим образом в COQ:

Inductive list (A:Set) : Set :=
  | nil : list A
  | cons : A -> list A -> list A.

Неформально list Тип - это самый маленький тип, который содержит все значения, построенные из nil а также cons Конструкторы, с аксиомой, что $ forall x , y, : mathtt {nil} ne mathtt {cons} : x : y $. И наоборот, мы можем определить самый большой тип, который содержит все значения, построенные из этих конструкторов, сохраняя аксиому дискриминации:

CoInductive colist (A:Set) : Set :=
  | conil : colist A
  | cocons : A -> colist A -> colist A.

list Изоморфно для подмножества colist. Анкет Кроме того, colist содержит бесконечные списки: списки с cocons на cocons.

CoFixpoint flipflop : colist ℕ := cocons 1 (cocons 2 flipflop).
CoFixpoint from (n:ℕ) : colist ℕ := cocons n (from (1 + n)).

flipflop это бесконечный (круговой список) $ 1 :: 2 :: 1 :: 2 :: ldots $; from 0 это бесконечный список натуральных чисел $ 0 :: 1 :: 2 :: ldots $.

Рекурсивное определение хорошо сформировано, если результат построен из меньших блоков: рекурсивные вызовы должны работать на более мелких входах. Корекурсивное определение хорошо сформировано, если результат создает большие объекты. Индукция смотрит на конструкторы, Coinduction смотрит на деструкторы. Обратите внимание, что двойственность не только изменяется на меньшую до большего, но и входы на выходы. Например, причина flipflop а также from Определения выше хорошо сформированы, что корекурсивный вызов охраняется призывом к cocons конструктор в обоих случаях.

В тех случаях, когда утверждения об индуктивных объектах имеют индуктивные доказательства, утверждения о коинтернативных объектах имеют коинктивные доказательства. Например, давайте определим бесконечный предикат на колистах; Интуитивно, бесконечные колисты - это те, которые не заканчиваются conil.

CoInductive Infinite A : colist A -> Prop :=
  | Inf : forall x l, Infinite l -> Infinite (cocons x l).

Чтобы доказать, что Колисты формы from n бесконечны, мы можем рассуждать по коиндукции. from n равно cocons n (from (1 + n)). Анкет Это показывает, что from n больше, чем from (1 + n), что бесконечено гипотезой по информированию, следовательно, from n бесконечно.

Битимилар, коинтернативная собственность

Коиндукция как техника доказательства также применяется к финальным объектам. Интуитивно говоря, индуктивные доказательства объекта основаны на том, как строится объект. Коунктивные доказательства основаны на том, как объект может быть разложен.

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

НЕТЕТЕРМИНГИЧЕСКИЕ СИСТЕМЫ, такие как одновременные системы, часто моделируются Маркированные переходные системы. Анкет LTS - это направленный график, на котором маркируются края. Каждый край представляет возможный переход системы. След LTS - это последовательность краевых меток по пути на графике.

Два LT могут вести себя одинаково, поскольку они имеют одинаковые возможные следы, даже если их внутренняя структура отличается. Изоморфизм графика слишком силен, чтобы определить их эквивалентность. Вместо этого, как говорят симулировать Другой lts $ mathscr {b} $, если каждый переход второго LTS допускает соответствующий переход в первом. Формально, пусть $ s $ будет непрерывным профсоюзом государств двух LTS, $ l $ (общий) набор ярлыков и $ rightarrow $ Отношение $ r subteq s times s $ является моделированием, если $$ forall (p, q) in r, % forall p ' in s, forall alpha in l, text {if} P StackRel alpha rightarrow p ' text {there} exists q', ; Q StackRel alpha rightarrow Q ' text {и} (p', q ') in r $$

$ mathscr {a} $ моделирует $ mathscr {b} $, если есть симуляция, в которой все состояния $ mathscr {b} $ связаны с состоянием в $ mathscr {a} $. Если $ r $ является симуляцией в обоих направлениях, это называется бизимуляция. Анкет Моделирование - это коинтерное свойство: любое наблюдение с одной стороны должно иметь совпадение с другой стороны.

В LTS потенциально много бизимуляций. Различные бизимуляции могут идентифицировать разные состояния. Учитывая два бизимуляции $ r_1 $ и $ r_2 $, отношение, приведенное путем принятия профсоюза графов отношений $ r_1 cup R_2 $ сама является бизимуляцией, поскольку связанные состояния приводят к смежным состояниям для обоих отношений. (Это также для бесконечных профсоюзов. Пустое отношение является бизимуляцией неинтерзистической, как и отношение идентичности.) В частности, союз всех бизимуляций сама по себе является бизимуляцией, называемой битимиларностью. Бисимилар - это самый грубый способ наблюдения за системой, которая не различает отдельные состояния.

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

использованная литература

  • COQ и исчисление индуктивных конструкций

    • Ив Берто и Пьер Кастеран. Интерактивная теорема Доказательство и разработка программы - Coq'art: исчисление индуктивных конструкций. Анкет Springer, 2004. Ch. 13. [Веб-сайт] [Амазонка]
    • Эдуардо Гименес. Применение совместных типов в COQ: Проверка протокола переменного бита. Анкет В Семинар по типам для доказательств и программ, номер 1158 в Заметки на лекции в информатике, страницы 135–152. Springer-Verlag, 1995. [Google Books]
    • Эдуардо Гименес и Пьер Кастеран. Учебное пособие по [ко-] индуктивным типам в Coq. 2007. [PDF]

  • Замеченные переходные системы и бизимуляции

    • Робин Милнер. Общение и параллелизм. Анкет Прентис Холл, 1989.
    • Давиде Сангиорги. О происхождении бизимуляции и коиндукции. Анкет Транзакции ACM на языках и системах программирования (Toplas), том 31 Выпуск 4, май 2009 г. [PDF] [ACM] Связанные слайды курса: [PDF] [Citeseer]

    • Давиде Сангиорги. Pi-Calculus: теория мобильных процессов. Анкет Издательство Кембриджского университета, 2003. [Амазонка]

    • А глава в Сертифицированное программирование с зависимыми типами А. Члипала

    • Д. Сангиорги. «Введение в бизимуляцию и коиндукцию». 2011. [PDF]
    • Д. Сангиорги и Дж. Руттен. Расширенные темы по бизимуляции и коиндукции. Анкет Издательство Кембриджского университета, 2012. [ЧАШКА]

Другие советы

Давайте рассмотрим следующее индуктивное определение:

$ qquad displaystyle begin {Align*} & phantom { rightarrow} Quad varepsilon in mathcal {t} w in mathcal {t} Quad & rightarrow Quad aw in in Mathcal {t} aw in mathcal {t} Quad & rightarrow Quad Baw in mathcal {t} end {Align*} $

Что такое $ mathcal {t} $? Ясно, что набор строк без двух последующих $ b $, т.е.

$ qquad displaystyle mathcal {t} = { varepsilon, a, aa, ba, aaa, aba, dots } = mathcal {l} left (ba mid a)^* right) subteq sigma^*. $

Верно? Что ж, то, что нам нужно для этого, является безобидным предложением "и $ mathcal {t} $ - самый маленький набор, который выполняет эти условия". Правда, как иначе $ mathcal {t} = {a, b }^*$ тоже будет работать.

Но это больше, чем это. Напишите выше определение как (монотон) функция $ f: 2^{ sigma^ infty} to 2^{ sigma^ infty} $:

$ qquad f (t) = t cup { varepsilon } cup {aw mid w in t } cup {baw mid aw in t } $

Теперь $ mathcal {t} $ наименьшая фиксация $ f $. Фактически, поскольку $ f $ является монотонным, а $ left (2^{ sigma^ infty}, subteq right) $ - это Полная решетка, Хнастер-Тарски теорема говорит нам, что такая самая маленькая фиксированная точка существует и является правильным языком. Поскольку это работает с любым разумным индуктивным определением, мы обычно не говорим об этом. Это просто соответствует нашей интуиции: мы начинаем с $ { varepsilon } $ и применяем правила шаг за шагом; В пределах мы получаем $ mathcal {t} $.

Теперь мы переворачиваем вещи. Вместо того, чтобы сказать «если $ w $ включена, так же, так ли это $ aw $», мы говорим «если $ aw $ включена, так что, должно быть, было $ w $». Мы не можем перевернуть якорь, так что он уходит. Это оставляет нас с проблемой: мы должны иметь возможность взять произвольно длинный Префиксы от любого слова в $ mathcal {t} '$ и остаются в $ mathcal {t}' $! Это невозможно с конечными словами; Хорошо, что я проник в $ sigma^ infty $ выше! В итоге мы получаем набор бесконечных слов без фактора (подстроения) $ bb $, то есть $ mathcal {t} '= mathcal {l} left ((ba mid a)^ omega right) $.

С точки зрения $ f $, $ mathcal {t} '$ крупнейший fixpoint². Это на самом деле довольно интуитивно: мы не можем надеяться нанести $ mathcal {t} '$ от ниже, IE индуктивно, начиная с $ { varepsilon } $ и добавление вещи, которые выполняют правила, поэтому мы идем от выше, т.е. коингульно, начиная с $ sigma^ infty $ и Удаление вещи, которые делают нет соответствовать правилам.

Обозначение:

  • $ Sigma^ infty = sigma^* cup sigma^ omega $
  • $ Sigma^ omega $ - это набор всех бесконечный Последовательности более $ sigma $.

¹ Вам не разрешено делать такие вещи, как $ w in mathcal {t} rightarrow a notin mathcal {t} $; Соответствующая функция не будет монотонной.
² Мы должны как -то подметать $ { varepsilon } $.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top