Использование алгебраических структур в теоретической информатике

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

В рамках теории групп я встречал синтаксические моноиды для формальных языков и моноиды трассировки и истории для параллельных / параллельных вычислений.

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

Мне еще предстоит найти какое-либо использование алгебраических структур из теории модулей в моих исследованиях (и я бы хотел).

Я предполагаю, что есть другие примеры, и я просто не ищу подходящее место, чтобы найти их.

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

У меня сложилось впечатление, что в целом традиционная алгебра слишком специфична для использования в компьютерных науках. Таким образом, ученые-компьютерщики либо используют более слабые (и, следовательно, более общие) структуры, либо обобщают традиционные структуры, чтобы они могли приспособить их к своим потребностям. Мы также используем теорию категории многочто математики не считают частью алгебры, но мы не понимаем, почему нет. Мы находим разделение традиционной математики на «алгебру» и «топологию» как отдельные ветви неудобным, даже бессмысленным, потому что алгебра, как правило, первого порядка, тогда как топология имеет шанс иметь дело с аспектами высшего порядка. Таким образом, структуры, используемые в информатике, смешивают алгебру и топологию. На самом деле, я бы сказал, что они больше склоняются к топологии, чем к алгебре. Регуляция рассуждений на «алгебру» и «логику» является еще одним бессмысленным делением с нашей точки зрения, потому что алгебра имеет дело с эквациональными свойствами, тогда как логика имеет дело и со всеми другими видами свойств.

Возвращаясь к вашему вопросу, полугруппы и моноиды довольно интенсивно используются в теории автоматов. Эйленберг написал сборник из 2 томов , второй из которых почти полностью является алгеброй. Мне сказали, что он планировал четыре тома, но его возраст не позволил завершить проект. Жан-Эрик Пин имеет модернизированную версию этого контента в онлайн-книге . Автоматы - это «моноидальные модули» (также называемые моноидными действиями или «действиями»), которые находятся на правильном уровне общности для компьютерных наук. Традиционные кольцевые модули, вероятно, слишком специфичны.

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

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

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

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

Дополнительное примечание : в конкретном смысле теория категорий является алгеброй. Моноид является фундаментальной структурой в алгебре. Он состоит из двоичного оператора «умножения», который является ассоциативным и имеет тождество. Теория категорий обобщает, связав «типов» к элементам моноида, . Вы можете "умножить" элементы только тогда , когда типы совпадают: если : X → Y и B : Y → Z , то б : X → Z . Например, n × $a : X \rightarrow Y$$a : X \rightarrow Y$$b : Y \to Z$$ab : X \to Z$$n \times n$матрицы имеют операцию умножения, что делает их моноидами. Однако матрицы (где m и n могут отличаться) образуют категорию. Таким образом, моноиды представляют собой особые случаи категорий, которые имеют один тип. Кольца - это особые случаи аддитивных категорий, которые имеют один тип. Модули - это особые случаи функторов, когда исходная и целевая категории имеют один тип. Скоро. Теория категорий - это типизированная алгебра , типы которой делают ее бесконечно более применимой, чем традиционная алгебра.$m \times n$$m$$n$

Мое любимое применение теории групп в TCS - теорема Баррингтона. Вы можете найти экспозицию этой теоремы в блоге сложности , а экспозицию Баррингтона - в разделе комментариев этого поста.

Группы, кольца, поля и модули повсюду в вычислительной топологии. См., В частности, работу Карлссона и Зомородяна [ex: 1 ] о (многомерных) постоянных гомологиях, которая касается градуированных модулей над главными идеальными областями.

Вот очень хорошее практическое использование: алгоритм для вычисления связности графа (из FOCS2011 ). Чтобы вычислить s-> t-связность графа, авторы дают алгоритм, который присваивает случайные векторы с записями из конечного поля внешним ребрам из s, а затем строит одинаковые векторы для всех ребер в графе, выбирая случайные линейные комбинации, и, наконец, обнаружение связности путем вычисления ранга результирующих векторов, назначенных ребрам t.

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

В распределенных вычислениях прославленное семейство результатов невозможности было получено с использованием методов алгебраической топологии (см. Работу Мориса Херлихи и Нира Шавита).

[Редактировать: См. Приложения Топологии к Информатике .]

Универсальная алгебра является важным инструментом в изучении сложности проблем удовлетворения ограничений.

Например, гипотеза дихотомии утверждает, что, грубо говоря, проблема удовлетворения ограничения в конечной области является либо NP-полной, либо разрешимой за полиномиальное время. Обратите внимание, что по теореме Ладнера существуют проблемы в NP, которые не находятся в P и не являются NP-полными, если только P = NP, поэтому гипотеза говорит о том, что CSP имеют особую дихотомию, которой нет в классах большей сложности. Это также дало бы некоторое объяснение, почему большинство проблем, с которыми мы сталкиваемся на практике, могут быть классифицированы как NP-полные или как P.

Дихотомии были доказаны для нескольких особых случаев, например CSP бинарного домена (Schaefer) и CSP троичного домена (Bulatov), ​​и гомоморфизмы в неориентированные графы (Hell и Nesetril). Но общий случай довольно открытый. Одна из главных линий атаки - универсальная алгебра. Очень приблизительно (и я определенно не эксперт в этом!) Каждый определяет полиморфизм CSP как функцию в области CSP, которая оставляет все удовлетворенные ограничения удовлетворенными, если он применяется к каждой переменной. Множество полиморфизмов CSP в некотором смысле отражает его сложность. Например, если CSP A допускает все полиморфизмы CSP B, то A за полиномиальное время сводится к B. Множество полиморфизмов образует алгебру, структура которой кажется полезной при определении алгоритмов / отображении сокращений. Например, если алгебра полиморфизма CSP является идемпотентной и допускает унарный тип, то CSP является NP-полной. Идемпотентность - это упрощенное предположение, которое можно сделать более или менее без потери общности. Показано, что CSP, алгебра которого идемпотентна и не допускает унарный тип, может быть решена за полиномиальное время, докажет гипотезу дихотомии.

Смотрите опрос Булатова: http://www.springerlink.com/content/a553847g6h673k05/ .

Вот два приложения из другой части TCS.

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

• Тодд Дж. Грин, Григорис Карвунаракис и Валь Таннен. Полукольца Provenance , PODS 2007. doi: 10.1145 / 1265530.1265535 ( препринт )
• Стефано Бистарелли, Уго Монтанари и Франческа Росси. Удовлетворение и оптимизация ограничений на основе полукольца , JACM 1997. doi: 10.1145 / 256303.256306 ( препринт )

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

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

В мире декодирования списков недавняя статья Guruswami дает линейно-алгебраический метод декодирования списков свернутых кодов Рида-Соломона, который обладает приятным свойством, заключающимся в том, что все сообщения-кандидаты находятся в низкоразмерном аффинном подпространстве пространства сообщений. , Можно построить подпространственные уклончивые множества , множества, которые почти такие же большие, как все пространство, но имеют небольшое пересечение с каждым низкоразмерным аффинным подпространством. Если кто-то ограничивает сообщения, приходящие из подпространственного уклоняющегося набора внутри пространства сообщений, то схема Гурусвами дает алгоритм, который гарантирует хороший размер списка. Пока единственное явное построение подпространственных уклончивых множеств дано Двиром и Ловеттом в их следующей статье STOC, Подпространственное уклончивое множество и построить набор, взяв определенный аффинный сорт (и взяв его декартово произведение с собой).

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

Эта статья выглядит как хорошее место для знакомства с информатикой, но вы можете поискать больше в Google. По своей сути он более комбинаторный, чем алгебраический, но имеет много применений в алгебре и теоретической CS.

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

Анализ любой проблемы с большой симметрией облегчается с помощью теории групп. Примером может служить поиск алгоритмов для таких вещей, как кубик Рубика. Хотя я не знаю деталей, я уверен, что доказательство того, что число Бога равно 20, потребовало некоторой серьезной групповой теоретической обрезки. В другом контексте, практические решатели для задачи изоморфизма графа, такие как nauty, используют группу автоморфизмов графа.

$\mathbb{Z}_p$

В функциональном программировании наиболее общие и изящные абстракции для задач часто имеют алгебраическую (или теоретико-категоричную) природу: моноиды, полукольца , функторы, монады, F-алгебры, F-коалгебры и т. Д. Некоторые классические результаты (например, Йонеда) лемма) случается иметь вычислительное содержание и полезность.

Кроме того, существует гомотопическая теория типов, которая интерпретирует теорию типов в (своего рода) алгебраической топологической среде.

В последнее время мы исследуем (см. Нашу статью о Springerlink: формальное последовательное объединение подходов к поиску часто встречающихся наборов ) в попытке объединения шаблонных подходов (популярный пример интеллектуального анализа данных) с помощью формальных рядов и взвешенных автоматов. Эти инструменты основаны на отображениях между моноидами и полукольцами.