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

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

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



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






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


Сибирские электронные математические известия, 2010, том 7, страницы 100–110 (Mi semr231)  

Статьи

Об автоматных и разрешимых линейных порядках

А. А. Гаврюшкина

Новосибирский государственный университет
Список литературы:
Аннотация: Let $\EuScript A$ be the class of automatic linear orderings, $\EuScript{AA}$ be the class of linear orderings which are computably categorical in the class of automatic presentation, $\EuScript{AD}$ be the class of linear orderings which are computably categorical in the class of decidable presentations. Obviously, $\EuScript{AD}\cap\EuScript A\subset\EuScript{AD}$. Since all automatic structures are decidable, $\EuScript{AD}\cap\EuScript A\subset\EuScript{AA}$, and one can easily see that $\EuScript{AD}\cap\EuScript A$ is nonempty. We show that there exist a linear order $\mathcal L_1\in\EuScript{AA}$ such that $\mathcal L_1\notin\EuScript{AD}$ and a linear order $\mathcal L_2\in\EuScript{AD}$ such that $\mathcal L_2\notin\EuScript A$. By this, the inclusions $\EuScript{AD}\cap\EuScript A\subset\EuScript{AD}$ and $\EuScript{AD}\cap\EuScript A\subset\EuScript{AA}$ are proper. In addition, we construct an example of a non–automatic linear order which is decidable in the language with the additional quantifier $\exists^\infty$.
Ключевые слова: automatic structure, decidable structure, linear ordering, computable categoricity.
Поступила 4 марта 2010 г., опубликована 20 апреля 2010 г.
Реферативные базы данных:
Тип публикации: Статья
УДК: 510.51
MSC: 03C57
Образец цитирования: А. А. Гаврюшкина, “Об автоматных и разрешимых линейных порядках”, Сиб. электрон. матем. изв., 7 (2010), 100–110
Цитирование в формате AMSBIB
\RBibitem{Gav10}
\by А.~А.~Гаврюшкина
\paper Об автоматных и разрешимых линейных порядках
\jour Сиб. электрон. матем. изв.
\yr 2010
\vol 7
\pages 100--110
\mathnet{http://mi.mathnet.ru/semr231}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2610169}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/semr231
  • https://www.mathnet.ru/rus/semr/v7/p100
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Статистика просмотров:
    Страница аннотации:257
    PDF полного текста:60
    Список литературы:42
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024