КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ


Номер проекта 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