Записки научных семинаров ПОМИ
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Записки научных семинаров ПОМИ, 1992, том 202, страницы 116–134 (Mi znsl1727)  

О некоторых проблемах теории сложности вычислений, связанных с алгебрами отношений

И. Н. Пономаренко
Аннотация: Когерентной алгеброй называется матричная алгебра над полем комплексных чисел, содержащая единичную матрицу и матрицу, состоящую из единиц, и инвариантная относительно эрмитова сопряжения и аданарова умножения. Известно, что когерентная алгебра обладает стандартным линейным базисом, состоящим из $(0,1)$-матриц. Семейство отношений конечного множества определяет алгебру отношений, если все члены этого семейства могут быть получены объединениями отношений, матрицы смежности которых являются стандартным базисом некоторой когерентной алгебры. Алгебры отношений возникают при изучении проблемы изоморфизма графов.
В настоящей работе рассматриваются основные проблемы, связанные с оценкой сложности базовых алгоритмов для работы с алгебрами отношений. В их число входят алгоритмы вычисления стандартного базиса алгебры отношений, пересечения и объединения алгебр. Кроме того, описан подход к проблеме изоморфизма графов, основанный на концепции Шуровых алгебр отношений (соответствующие им когерентные алгебры являются централизаторными алгебрами групп перестановок). Статья завершается списком открытых проблем и обсуждением возможных направлений дальнейших исследований. Библ.: 18 назв.
Англоязычная версия:
Journal of Mathematical Sciences, 1996, Volume 79, Issue 3, Pages 1105–1114
DOI: https://doi.org/10.1007/BF02366131
Реферативные базы данных:
УДК: 519.5
Образец цитирования: И. Н. Пономаренко, “О некоторых проблемах теории сложности вычислений, связанных с алгебрами отношений”, Численные методы и вопросы организации вычислений. IX, Зап. научн. сем. ПОМИ, 202, Наука, СПб., 1992, 116–134; J. Math. Sci., 79:3 (1996), 1105–1114
Цитирование в формате AMSBIB
\RBibitem{Pon92}
\by И.~Н.~Пономаренко
\paper О~некоторых проблемах теории сложности
вычислений, связанных с~алгебрами отношений
\inbook Численные методы и вопросы организации вычислений.~IX
\serial Зап. научн. сем. ПОМИ
\yr 1992
\vol 202
\pages 116--134
\publ Наука
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl1727}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1259291}
\zmath{https://zbmath.org/?q=an:0844.68047|0807.68036}
\transl
\jour J. Math. Sci.
\yr 1996
\vol 79
\issue 3
\pages 1105--1114
\crossref{https://doi.org/10.1007/BF02366131}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/znsl1727
  • https://www.mathnet.ru/rus/znsl/v202/p116
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Статистика просмотров:
    Страница аннотации:205
    PDF полного текста:79
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024