Усилия по проверке компилятора часто сводятся к тому, чтобы доказать, что компилятор полностью абстрактен: он сохраняет и отражает (контекстуальные) эквивалентности. Вместо того, чтобы предоставлять полные доказательства абстракции, некоторые недавние (основанные на категориях) работы по проверке...
Функциональный язык можно рассматривать как категорию, где его объектами являются типы и функции морфизмов между ними. Как классы типов вписываются в эту модель? Я предполагаю, что мы должны рассматривать только те реализации, которые удовлетворяют ограничению, которое имеет большинство классов...
Есть ли категория патчей, которая выглядит примерно так: Объекты являются строками в некотором базовом алфавите Морфизмы - это скрипты редактирования ("diffs" или "patches") между строками Я заинтересован в следующих вопросах: Есть ли категорическое понятие минимального сценария редактирования?...
Поскольку мне интересны парсеры (в основном грамматики выражений парсеров), мне интересно, есть ли какая-то работа, которая дает категорический подход к анализу. Любая ссылка на приложения теории категорий к синтаксическому анализу высоко ценится....
Я прочитал статью Фрейда «Алгебраически полные категории» в известной книге Como90, и у меня есть два вопроса о понятии алгебраической компактности, которое он определил в этой статье. (Если вы не знакомы с определением, вот оно: категория называется алгебраически компактной, если каждый...
Существуют ли NP-полные (или даже NP-сложные, или NP) задачи, которые имеют хорошие топологические свойства для изучения. Есть ли у задач NP теоретические формулировки узлов? Мы знаем о результатах # о полиноме Джонса. Графические задачи (вложения?), В частности раскраски графов, могут иметь...
\newcommand{\symp}{\Bumpeq} ≎X≎X\symp_XXXX(X,≎X)(X,≎X)(X, \symp_X)f:X→Yf:X→Yf : X \to Yf⊆X×Yf⊆X×Yf \subseteq X \times Y(x,y)∈f(x,y)∈f(x,y) \in f(x′,y′)∈f(x′,y′)∈f(x',y') \in f если то иx≎Xx′x≎Xx′x \symp_X x'y≎Yy′y≎Yy′y \symp_Y y' если и то .x≎Xx′x≎Xx′x \symp_X x'y=y′y=y′y = y'x=x′x=x′x = x'...
Я не теоретик информатик. Я стабильный теоретик гомотопий, использующий -категории. Я видел применения теории категорий и теории топосов к теоретической информатике, и мне было интересно, можно ли каким-либо образом использовать -категории (и, предпочтительно, для меня, теория стабильной гомотопии)...
Учитывая endofunctor , мы можем определить функции наблюдения как функции , которые являются полиморфными для любого F -коалгебры, то есть о б ы определена для любого F -коалгебры ⟨ A , гр : A → F A ⟩ . о б ы : ∀ ⟨ А , с ⟩ . A → B Другой способ рассмотрения функций наблюдения - это функции...
В теоремах бесплатно! Вадлер говорит, что характеристика параметричности может быть выражена в терминах слабых естественных преобразований, и это будет предметом дальнейшей статьи. На какую бумагу он ссылается? Я знаю, что категорический подход к параметричности использует динатуральные...
Глядя на модели параметрического полиморфизма, мне интересно, почему используются рефлексивные категории графов ? В частности, почему они не включают реляционную композицию? При взгляде на модели все они, кажется, поддерживают естественное понятие реляционной композиции:...
Скажем, я работаю в теории гомотопического типа, и мои единственные объекты изучения - это условные категории. Эквивалентности здесь даны функторами F:D⟶CF:D⟶CF:{\bf D}\longrightarrow{\bf C} а также G:C⟶DG:C⟶DG:{\bf C}\longrightarrow{\bf D}которые обеспечивают эквивалентность категорий C≃DC≃D{\bf...
Эквивалентно, существует ли известная денотационная семантика для вероятностных функциональных языков программирования высшего порядка? В частности, существует ли доменная модель чистого нетипизированного вычисления, расширенная симметричной случайной операцией двоичного выбора.λλ\lambda мотивация...
У меня есть следующая типизированная теория |- 1_X : X -> X f : A -> B, g : B -> C |- compose(g,f) : A -> C F, f : A -> B |- apply(F,f) : F(A) -> F(B) с уравнениями для всех членов: f : A -> B, g : B -> C, h : C -> D |- compose(h,compose(f,g)) = compose(compose(h,f),g) f...
Имея дело с теоретико-областными категориями (скажем, CPO и CPO), я часто хотел бы найти словарь для языка теории категорий в теории областей.ωω\omega То есть, учитывая концепцию, скажем, моническую стрелку, я мог бы найти ее в словаре и посмотреть, каковы ее известные характеристики в разных...
Мне интересно узнать, как мы можем использовать концепции пределов и колимитов в задачах моделирования в повседневной жизни? Может быть, кто-нибудь может привести примеры разработки программного обеспечения? Или опишите интуитивно в целом, для каких задач моделирования мы можем использовать эти...
Этот вопрос по сути является вопросом, который я задал на Mathoverflow. Логика Монадического Второго Порядка (MSO) - это логика второго порядка с количественным определением по унарным предикатам. То есть количественное определение по множествам. Есть несколько логик MSO, которые являются...
Функторы, построенные из конечных произведений и сумм, имеют порядковый номер замыкания ωω\omegaподробно описанный в этой рукописи Франсуа Метайера. т.е. мы можем достичь индуктивного типаnat:=μX.1+XNaTзнак равноμИкс,1+Иксnat := \mu X. 1 + X перебирая функтор 1 + Х1+Икс1 + X, которая достигает...