Применение топологии в информатике

61

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

  1. Существуют ли какие-либо статьи или заметки, описывающие хронологию использования топологии в информатике?

  2. Каковы наиболее важные приложения результатов в топологии для компьютерных наук?

  3. Каковы наиболее интересные области текущей работы, которые используют топологию, чтобы получить представление о вычислениях?

Спасибо!

Бен
источник
8
Несколько ответов на этот другой вопрос актуальны здесь: cstheory.stackexchange.com/questions/1920/…
Джошуа
1
как насчет работы над алгоритмами для вычисления топологических объектов или использования топологических конструкций для моделирования данных? это считается?
Суреш Венкат
7
Это будет длинный опрос.
Джеффс
2
Вам удалось? Ссылка на ваш опрос будет оценена!
Тарк
Это сообщение о симпатичном применении топологии к программированию: math.andrej.com/2007/09/28/…
Холден Ли

Ответы:

33

Лично я думаю, что наиболее интересным применением топологии была работа, выполненная Херлихи и Шавитом. Они использовали алгебраическую топологию для характеристики асинхронных распределенных вычислений, дали новые доказательства важных известных результатов и устранили ряд давних открытых проблем. За эту работу они выиграли приз Годеля 2004 года.

«Топологическая структура асинхронных вычислений» Мориса Херлихи и Нира Шавита, журнал ACM, Vol. 46 (1999), 858-923,

Марк Рейтблатт
источник
5
"Самое интересное" ? теперь они борются за слова! :)
Суреш Венкат
28

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

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

  1. Теорема компактности пропозициональной логики является следствием теоремы Тихонова. Компактность для логики первого порядка обычно доказывается по-разному. Компактность является важным инструментом в классической теории моделей.

  2. Теорема Стоуна о представлении булевых алгебр связывает модели логики высказываний, булевых алгебр и некоторых топологических пространств. Результаты двойственности типа камня были получены для структур, используемых в алгебраической логике и семантике языка программирования.

  3. Ник Пиппенгер применил теорему Стоуна к булевой алгебре регулярных языков и использовал топологию для доказательства нескольких фактов о регулярных языках. См. Комментарий Жан-Эрика Пина для более поздней работы над топологией в теории языка.

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

  5. Мартин Эскардо разработал алгоритмы и написал программы для поиска бесконечных множеств. Я считаю, что компактность является ключевым компонентом этой работы.

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

  7. Операторы замыкания и другие топологические идеи являются основой математической морфологии.

  8. Понятие внутренних операторов также из польской школы важно для аксиоматизации модальной логики.

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

  10. Возможно, приложение, которое получает наибольшее количество прессы, - это приложение топологии (изначально алгебраическое, хотя также существует больше комбинаторных представлений) для характеристики определенных сценариев отказоустойчивости в распределенных вычислениях. В дополнение к Херлихи и Шавиту, упомянутым выше, Боровский и Гафни, а также Сакс и Захароглу также высказались за первый такой прорыв. Структура асинхронной вычислимости дала больше таких результатов.

  11. Теорема Брауэра о неподвижной точке породила несколько проблем, которые мы изучаем. В последнее время в исследовании алгоритмической теории игр, класс сложности PPAD и класс сложности FixP задач с фиксированной точкой.

  12. Теорема Борсука-Улама имеет несколько приложений для графов и метрических вложений. Они описаны в книге Иржи Матушека.

Это скудный выбор на то, что там. Удачи!

Виджай Д
источник
Какой отличный список!
Дейв Кларк,
24

Теория предметной области имеет высокую топологическую природу и, скорее, является одноразовым применением топологии, но в большей или меньшей степени является ее собственным подполем топологии. Его применение в денотационной семантике языков программирования, особенно функциональных, безусловно, является одним из наиболее важных приложений топологии в информатике. Значения (включая функции) задаются семантикой в ​​терминах DCPO (направленные-полные частичные порядки) или некоторой такой структуры. В этой настройке можно решить уравнения рекурсивной области, такие как , предоставляя семантику таким животным, как нетипизированныйλD[DD]λ-исчисление. Семантика в основном основана на понятии приближения, заданном порядком, и решении уравнений с наименьшей неподвижной точкой, и решения, как правило, гарантированно существуют.

От денотационной семантики вытекают связи с абстрактной интерпретацией, анализом и верификацией программ.

Текущее исследование включает обеспечение денотационной семантики для параллелизма и для квантовых языков.

Абрамский и Юнг дают хороший обзор основных идей: теория доменов .

Дэйв Кларк
источник
18

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

Майкл Бен-Ор, Нижние оценки для деревьев алгебраических вычислений, STOC 1983, с. 80-86.

Andrew Chi-Chih Yao, Сложность дерева решений и числа Бетти, J. Comput. System Sci. 55 (1997), нет. 1, часть 1, 36-43 (STOC 1994).

Андерс Бьорнер и Ласло Ловаш. Линейные деревья решений, подпространственные схемы и функции Мёбиуса, J. ​​Amer. Математика Soc. 7 (1994), нет. 3, 677-706.


В другом, но несколько связанном ключе Смейл использовал топологию довольно интересным образом (в частности, когомологии группы кос), чтобы понизить границу сложности поиска корней в модели Блюма-Шуб-Смейла:

Смейл, С. О топологии алгоритмов, IJ Complexity, 3 (2): 81-89, 1987.

Джошуа Грохов
источник
Эти ссылки кажутся относительно старыми. Было ли продолжающееся направление исследований, или это были довольно одноразовые результаты?
Марк Рейтблатт
Ну, я бы не назвал их одноразовыми, так как эти методы дали кучу результатов. Я думаю, что в более современных результатах (скажем, за последнее десятилетие) либо используются совершенно разные методы, либо они используют больше аспекта полуалгебраической геометрии, чем топологический аспект.
Джошуа Грохов
(Я не знаю о вопросе Марка относительно результата Смейла.)
Джошуа Грохов
18

Вычислимый анализ и вычислимость более .2ω

Это связано с ответом Дейва и теорией предметной области. Основной аргумент здесь заключается в том, что вычислимость по своей природе основана на локальных операциях и конечных наблюдениях . Вы можете думать о вычислимости как об уточненном понятии топологии. Наиболее наглядным примером является то, что:

Все вычислимые функции (оракула Тьюринга) являются непрерывными. С другой стороны, каждая непрерывная функция вычисляется с помощью подходящего оракула.

Вы можете найти больше в книге Клауса Вейрауха «Вычислительный анализ». Вы также можете взглянуть на красивую книгу Стивена Викерса «Топология через логику».

Кава
источник
15

Два других документа, которые могут иметь отношение к вашему опросу ...

М. Герке, С. Григорьев, Ж.-Е. Pin, Топологический подход к распознаванию, ICALP 2010, Часть II, Конспект лекций в области компьютерных наук 6199, Springer Verlag, (2010), 151-162.

М. Герке, С. Григорьев, Ж.-Е. Пин, Двойственность и теория эквациональных регулярных языков, Награда за лучшую статью ICALP 2008, Трек B, ICALP 2008, Часть II, Конспект лекций в области компьютерных наук 5126, Springer Verlag, (2008), 246-257.

Жан-Эрик Пин
источник
3
Добро пожаловать! Мне очень понравилась ваша обзорная статья "Профилактические методы в теории автоматов".
Нил Кришнасвами
14

Не забывайте гипотезу Кнезера и доказательство Канна-Сакса-Стертеванта для гипотезы Аандеры-Розенберга-Карпа.

Суреш Венкат
источник
14

Не видел упомянутых работ Роберта Гриста , который раньше работал в Иллинойсе, а теперь в У Пенне, применяя топологию к таким вещам , как сенсорные сети и робототехника. Вот хорошее интервью.

Также очень связано с работой Гуннара Карлссона и др. По применению топологии для анализа данных .

Возможно, не STOC / FOCS TCS, но определенно информатика.

Мугизи Рвебангира
источник
13

Теории для понимания параллелизма и моделирования параллельных вычислений лучше всего понять топологически. Помимо известной работы Херлихи и Шавита о топологической структуре асинхронной вычислимости, упомянутой в предыдущем ответе, Эрик Губо проделал работу по моделированию параллелизма с геометрией и работу Пратта по применению пространств Чу для параллелизма в группе параллелизма Стэнфорда. хотя я не знаком с их работой.

Kryptos
источник
12

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

Есть также несколько низкоразмерных топологических подходов к темам в теории вычислений, все они довольно новые:

  • Различные подходы к отказоустойчивым аноническим квантовым вычислениям основаны на теории кос. Смотрите, например, ЗДЕСЬ и ЗДЕСЬ . Также к сетям адиабатических квантовых вычислений ЗДЕСЬ .
  • Диаграмматические формализмы, основанные на топологии, для лямбда-исчисления (например, ЗДЕСЬ , стр. 46-48 и ЗДЕСЬ ) и для пи-вычисления Мильнера ( ЗДЕСЬ ).
  • Использование конкатенации цветных связок для моделирования рекурсивных и марковских цепей. Смотрите, например, ЗДЕСЬ и ЗДЕСЬ . Фактически доказано (неопубликовано), что таким способом можно моделировать любые вычисления машины Тьюринга и любую рекуррентную нейронную сеть первого порядка.
  • Существует более высокий класс теоретического формализма для квантовых вычислений, в котором топологические диаграммы представляют вычисления, а топологически эквивалентные диаграммы представляют различные процедуры с одинаковым вычислительным содержанием. Смотри ЗДЕСЬ .
Даниил Москович
источник
11

Некоторые приложения для метрических вложений.

Проверьте эту книгу Matousek: http://kam.mff.cuni.cz/~matousek/akt.html

Также проверьте эти документы:

  • Би-липшицевы вложения в низкоразмерные евклидовы пространства, J. ​​Matousek (1990) (он использует теорему Ван Кампена для доказательства нижней границы)
  • Неподходимость для метрических вложений в R ^ d, J. Matousek и A. Sidiropoulos
Zouzias
источник
10

прочитайте эту книгу:

Посмотреть его архивную веб-страницу

БРЗ
источник
Я не знаю, действительно ли вычислительная топология - то, что он ищет. Есть ли там приложения вне вычислительной топологии?
Марк Рейтблатт
8
Мммм. Да. В книге Афры подробно рассматриваются реконструкция поверхности и удаление топологического шума (которые имеют приложения в компьютерной графике), но есть также применения вычислительной топологии в анализе многомерных данных, обучении множеству, компьютерному зрению, обработке изображений, уменьшению размерности, поиску информации, движению планирование и т. д. и т. д.
Джеффс
8

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

PNPPNPNPPNPNPP

Мухаммед Аль-Туркистани
источник
4
На самом деле, была проделана большая работа над p-мерой и p-категорией (о чем говорит туркистания). Джек Латс представил эту идею, и вы можете найти тонну статей, отыскав его, перейдя по ссылкам на соавторов и пересылкам.
Джошуа Грохов