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

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

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.

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

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

Тип публикации: Статья
УДК: 510.51
MSC: 03C57
Поступила 4 марта 2010 г., опубликована 20 апреля 2010 г.

Образец цитирования: А. А. Гаврюшкина, “Об автоматных и разрешимых линейных порядках”, Сиб. электрон. матем. изв., 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://www.ams.org/mathscinet-getitem?mr=2610169}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr231
  • http://mi.mathnet.ru/rus/semr/v7/p100

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:161
    Полный текст:41
    Литература:16

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