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

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

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



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






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


Матем. заметки, 2003, том 74, выпуск 1, страницы 69–75 (Mi mz246)  

О полиномиальной вычислимости некоторых рудиментарных предикатов

С. С. Марченков

Московский государственный университет им. М. В. Ломоносова

Аннотация: Класс рудиментарных предикатов определяется как наименьший класс числовых предикатов, который содержит предикаты равенства и конкатенации и замкнут относительно операций логики высказываний, явных преобразований и навешивания ограниченных кванторов. Рассматриваются два класса рудиментарных предикатов. Первый класс состоит из предикатов, которые имеют в предваренной нормальной форме специального вида кванторную приставку типа $\exists\forall$. У предикатов второго класса кванторная приставка может быть произвольной, но ограничения налагаются на скулемовские разрешающие функции. Доказывается, что любой предикат каждого из этих классов можно вычислить подходящим детерминированным алгоритмом за полиномиальное время.
Библиография: 8 названий.

DOI: https://doi.org/10.4213/mzm246

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

Англоязычная версия:
Mathematical Notes, 2003, 74:1, 64–69

Реферативные базы данных:

УДК: 519.712
Поступило: 17.01.2001

Образец цитирования: С. С. Марченков, “О полиномиальной вычислимости некоторых рудиментарных предикатов”, Матем. заметки, 74:1 (2003), 69–75; Math. Notes, 74:1 (2003), 64–69

Цитирование в формате AMSBIB
\RBibitem{Mar03}
\by С.~С.~Марченков
\paper О~полиномиальной вычислимости некоторых рудиментарных предикатов
\jour Матем. заметки
\yr 2003
\vol 74
\issue 1
\pages 69--75
\mathnet{http://mi.mathnet.ru/mz246}
\crossref{https://doi.org/10.4213/mzm246}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2010678}
\zmath{https://zbmath.org/?q=an:1077.03023}
\transl
\jour Math. Notes
\yr 2003
\vol 74
\issue 1
\pages 64--69
\crossref{https://doi.org/10.1023/A:1025067132637}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000185172900008}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-0345863693}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mz246
  • https://doi.org/10.4213/mzm246
  • http://mi.mathnet.ru/rus/mz/v74/i1/p69

    ОТПРАВИТЬ: 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
  • Математические заметки Mathematical Notes
    Просмотров:
    Эта страница:151
    Полный текст:58
    Литература:24
    Первая стр.:1

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019