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

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

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



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






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


Модел. и анализ информ. систем, 2018, том 25, номер 5, страницы 525–533 (Mi mais646)  

Прикладные логики

О безопасности одно- и многоместных IFP-операторов

С. М. Дудаков

Тверской государственный университет, ул. Желябова, 33, г. Тверь, 170100 Россия

Аннотация: В работе изучается безопасность унарных операторов инфляционной неподвижной точки (IFP-операторов), то есть возможность их вычисления за конечное время. Такие операторы в точности соответствуют рекурсивным SQL-запросам, поэтому изучаемый вопрос имеет непосредственное отношение к базам данных. Исследуемая проблема возникает из-за того, что при одновременном применении в SQL запросе рекурсии и отношений универсума, например, сложения, может оказаться так, что процедура вычисления результата запроса зациклится. Более того, такая комбинация позволяет моделировать работу универсального вычислительного устройства, например, машины Тьюринга, поэтому вопрос о возможности вычисления SQL запроса за конечное время оказывается алгоритмически неразрешимым. В предыдущих работах были введены и изучены некоторые свойства универсумов, которые позволяют гарантировать возможность вычисления любых запросов за конечное время. Здесь мы изучаем вопрос о том, насколько существенна местность IFP-операторов в контексте их безопасности. Основным результатом настоящей работы является демонстрация того, что если ограничиться только унарными IFP-операторами, то не имеют места результаты, справедливые для IFP-операторов в общем случае без ограничения местности. Построен пример универсума, в котором все унарные IFP-операторы, не вложенные один в другой, безопасны. Вместе с тем в этом универсуме существуют небезопасные бинарные IFP-операторы, таким образом, при изменении местности безопасность может утрачиваться. Кроме того, существуют и небезопасные вложенные один в другой унарные операторы. Это контрастирует с общим случаем, в котором такое невозможно. Также существуют элементарно эквивалентные универсумы, в которых те же самые унарные IFP-операторы безопасными не являются. Такое поведение тоже отличается от поведения IFP-операторов произвольной местности.

Ключевые слова: инфляционная неподвижная точка, местность, безопасность.

DOI: https://doi.org/10.18255/1818-1015-525-533

Полный текст: PDF файл (511 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 517.9
Поступила в редакцию: 10.09.2018

Образец цитирования: С. М. Дудаков, “О безопасности одно- и многоместных IFP-операторов”, Модел. и анализ информ. систем, 25:5 (2018), 525–533

Цитирование в формате AMSBIB
\RBibitem{Dud18}
\by С.~М.~Дудаков
\paper О безопасности одно- и многоместных IFP-операторов
\jour Модел. и анализ информ. систем
\yr 2018
\vol 25
\issue 5
\pages 525--533
\mathnet{http://mi.mathnet.ru/mais646}
\crossref{https://doi.org/10.18255/1818-1015-525-533}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais646
  • http://mi.mathnet.ru/rus/mais/v25/i5/p525

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:42
    Полный текст:7
    Литература:8
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019