КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер проекта 18-11-00028
НазваниеАлгебраические структуры и вычислимость
Руководитель Калимуллин Искандер Шагитович, Доктор физико-математических наук
Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Казанский (Приволжский) федеральный университет" , Республика Татарстан (Татарстан)
Конкурс №28 - Конкурс 2018 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами»
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-101 - Математическая логика и основания математики
Ключевые слова вычислимая структура, вычислимо категоричная структура, линейный порядок, тьюринговая степень, оракульное вычисление.
Код ГРНТИ27.03.45
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
Проект направлен на исследование алгебраических структур с точки зрения их алгоритмической сложности и связанных с ними классами тьюринговых степеней. Наибольшее внимание будет уделено структурам с простейшими языками: графам, линейным порядкам и булевым алгебрам, поскольку они в достаточно полной мере отражают алгоритмическую сложность строения произвольной структуры. Связанные со структурами классы степеней будут, как правило, состоять из степеней оракулов, способных разрешить ту или иную алгоритмическую проблему в данной структуре, например проблему представимости структуры натуральными числами (спектр степеней). Актуальность этого подхода заключается, в частности, в том, что он с одной стороны может помочь разработать новые методы классификации алгебраических структур, а с другой стороны позволит обогатить арсенал средств классической теории вычислимости.
ОТЧЁТНЫЕ МАТЕРИАЛЫ
Публикации
1.
Калимуллин И.Ш., Пузаренко В.Г., Файзрахманов М.Х.
Позитивные представления семейств относительно сводимости по перечислимости
Алгебра и Логика, Т. 57, № 4, с. 492-498 (год публикации - 2018)
10.17377/alglog.2018.57.406
2. Калимуллин И.Ш., Кэч А., Монталбан А., Пузаренко В.Г., Файзрахманов М.Х. Jump inversions of algebraic structures and Sigma-definability Mathematical Logic Quarterly (год публикации - 2019)
3. Баженов Н.А. Спектры категоричности вычислимых структур Итоги науки и техники. Серия «Современная математика и ее приложения. Тематические обзоры» (переводится в Journal of Mathematical Sciences) (год публикации - 2018)
4.
Селиванов В.Л., Ямалеев М.М.
О тьюринговых степенях в уточнениях арифметической иерархии
Алгебра и логика, Т. 57, № 3, с. 338-361 (год публикации - 2018)
10.17377/alglog.2018.57.306
5. Калимуллин И.Ш., Селиванов В.Л., Фролов А.Н. Спектры степеней структур Итоги науки и техники. Серия «Современная математика и ее приложения. Тематические обзоры» (переводится в Journal of Mathematical Sciences) (год публикации - 2018)
6. Селиванов В.Л. Предполные нумерации Итоги науки и техники. Серия «Современная математика и ее приложения. Тематические обзоры» (переводится в Journal of Mathematical Sciences) (год публикации - 2018)
7. И.Ш. Калимуллин, М.Х. Файзрахманов О степенях перечислений счетных семейств вехнеровского типа Итоги науки и техники. Серия «Современная математика и ее приложения. Тематические обзоры» (переводится в Journal of Mathematical Sciences) (год публикации - 2019)
Публикации
1. Селиванов В.Л. On degree spectra of topological spaces Lobachevskii Journal of Mathematics (год публикации - 2020)
2.
Зубков М.В., Калимуллин И.Ш., Мельников А.Г., Фролов А.Н.
Пунктуальные копии алгебраических структур
Сибирский математический журнал, Том 60, № 6, стр. 1271-1285. (год публикации - 2019)
10.33048/smzh.2019.60.607
3.
Баженов Н.А., Мустафа М., Ямалеев М.М.
Computable isomorphisms of distributive lattices
Lecture Notes in Computer Science, Том 11436, стр. 28–41. (год публикации - 2019)
10.1007/978-3-030-14812-6_3
4.
Баженов Н.А., Доуни Р., Калимуллин И.Ш., Мельников А.Г.
Foundations of online structure theory
Bulletin of Symbolic Logic, Том 25, № 2, стр. 141-181. (год публикации - 2019)
10.1017/bsl.2019.20
5.
Нг. К.М., Зубков М.В.
On Kierstead's conjecture
Transactions of the American Mathematical Society, Том 372, № 5, стр. 3713-3753. (год публикации - 2019)
10.1090/tran/7858
6.
Александрова С.А., Баженов Н.А.
О разрешимости списочных структур
Сибирский математический журнал, Том 60, № 3, стр. 489–505. (год публикации - 2019)
10.33048/smzh.2019.60.302
7.
Калимуллин И.Ш., Пузаренко В.Г., Файзрахманов М.Х.
Частичные разрешимые представления в гиперарифметике
Сибирский математический журнал, Том 60, № 3, стр. 599–609. (год публикации - 2019)
10.33048/smzh.2019.60.309
8. Калимуллин И.Ш., Пузаренко В.Г., Файзрахманов М.Х. О позитивных и однозначных вычислимых нумерациях в гиперарифметике Алгебра и логика (год публикации - 2020)
9. Файзрахманов М.Х. Решеточные свойства полурешеток Роджерса вычислимых и обобщенно вычислимых семейств Сибирские электронные математические известия (год публикации - 2020)
10. Баженов Н.А., Калимуллин И.Ш., Ямалеев М.М. Strong degrees of categoricity and weak density Lobachevskii Journal of Mathematics (год публикации - 2020)
11. Мельников А.Г., Селиванов В.Л., Ямалеев М.М. Turing reducibility in the fine hierarchy Annals of Pure and Applied Logic (год публикации - 2020)
12.
Баженов Н.А., Харрисон-Трейнор М., Калимуллин И.Ш., Мельников А.Г., Нг К.М.
Automatic and polynomial-time algebraic structures
Journal of Symbolic Logic (год публикации - 2019)
10.1017/jsl.2019.26
13.
Калимуллин И.Ш., Миллер Р.
Primitive recursive fields and categoricity
Algebra and Logic, Том 58, № 1, стр. 95–99. (год публикации - 2019)
10.1007/s10469-019-09527-1
14.
Калимуллин И.Ш., Миллер Р., Шоутенс Х.
Degree spectra for transcendence in fields
Lecture Notes in Computer Science, Том 11558, стр. 205-216. (год публикации - 2019)
10.1007/978-3-030-22996-2_18
15. Баженов Н.А., Мустафа М., Сан Мауро Л., Ямалеев М.М. Minimal equivalence relations in hyperarithmetical and analytical hierarchies Lobachevskii Journal of Mathematics (год публикации - 2020)
Публикации
1.
Баженов Н.А., Калимуллин И.Ш., Мельников А.Г., Нг К.М.
Online presentations of finitely generated structures
Theoretical Computer Science, Volume 844, Pages 195-216 (год публикации - 2020)
10.1016/j.tcs.2020.08.021
2.
Баженов Н.А., Мустафа М., Сан Мауро Л., Сорби А., Ямалеев М.М.
Classifying equivalence relations in the Ershov hierarchy
Archive for Mathematical Logic, Volume 59, Issue 7-8, Pages 835-864 (год публикации - 2020)
10.1007/s00153-020-00710-1
3.
Баженов Н.А., Фокина Е.Б., Россеггер Д., Сан Мауро Л.
Degrees of bi-embeddable categoricity
Computability (год публикации - 2020)
10.3233/COM-190289
4.
Баженов Н.А., Фокина Е.Б., Сан Мауро Л.
Learning families of algebraic structures from informant
Information and Computation, номер статьи 104590 (год публикации - 2020)
10.1016/j.ic.2020.104590
5.
Калимуллин И.Ш., Пузаренко В.Г., Файзрахманов М.Х.
Позитивные нумерации в допустимых множествах
Сибирский Математический Журнал, Том 61, № 3. - С. 607-621. (год публикации - 2020)
10.33048/smzh.2020.61.309
6.
Калимуллин И.Ш., Пузаренко В.Г., Файзрахманов М.Х.
Semidecidable Numberings in Admissible Sets
Algebra and Logic, Volume 59, Issue 3, Pages 273-277 (год публикации - 2020)
10.1007/s10469-020-09599-4
7. Калимуллин И.Ш., Мельников А.Г., Зубков М.В. Punctual Degrees And Lattice Embeddings Lecture Notes Series, IMS (год публикации - 2021)
8.
Доуни Р., Харрисон-Трейнер М., Калимуллин И.Ш., Мельников А.Г., Турецкий Д.
Graphs are not universal for online computability
Journal of Computer and System Sciences, Volume 112, Pages 1-12 (год публикации - 2020)
10.1016/j.jcss.2020.02.004
9. Абызов А.Н., Тапкин Д.Т. Simple-direct modules over formal matrix rings Lobachevskii Journal of Mathematics (год публикации - 2021)
10. Арсланов М.М. Fixed-point selection functions Lobachevskii Journal of Mathematics (год публикации - 2021)
11.
Калимуллин И.Ш.
О построении пунктуально категоричных полугрупп
Алгебра и логика, Том 59, № 5, стр. 600-605. (год публикации - 2020)
10.33048/alglog.2020.59.507
12. Пузаренко В.Г., Файзрахманов М.Х. Absolute and Relative Properties of Negatively Numbered Families Lobachevskii Journal of Mathematics (год публикации - 2021)
13. Калимуллин И.Ш., Мельников А.Г. Punctual categoricity relative to a computable oracle Lobachevskii Journal of Mathematics (год публикации - 2021)
14.
Хойруп М., Кихара Т., Селиванов В.Л.
Degrees of Non-computability of Homeomorphism Types of Polish Spaces
Lecture Notes in Computer Science, Volume 12098 LNCS, 2020, Pages 189-192 (год публикации - 2020)
10.1007/978-3-030-51466-2_16
15.
Зубков М.В., Фролов А.Н.
The simplest low linear order with no computable copies
Journal of Symbolic Logic, The Journal of Symbolic Logic, pp. 1-18. (год публикации - 2022)
10.1017/jsl.2022.44
16.
Файзрахманов М.Х.
On p-Universal and p-Minimal Numberings
Сибирский математический журнал, Volume 63, Issue 2, March 2022, Pages 365-373 (год публикации - 2022)
10.1134/S0037446622020148
17.
Баженов Н.А., Россеггер Д., Зубков М.В.
On bi-embeddable categoricity of algebraic structures
Annals of Pure and Applied Logic, Volume 173, Issue 3, March 2022, Номер статьи 103060 (год публикации - 2022)
10.1016/j.apal.2021.103060
18.
Баженов Н.А., Мустафа М.
Computable embeddability for algebraic structures
Asian-European Journal of Mathematics, Volume 15, Issue 7, 1 July 2022, Номер статьи 2250126 (год публикации - 2022)
10.1142/S1793557122501261