Доклад Александра Запрягаева "Арифметики Бюхи и конечные автоматы"
4 февраля в 18:30 состоится заседание исследовательского семинара "From the Logical Point of View" Международной лаборатории логики, лингвистики и формальной философии.
Александр Запрягаев
стажер-исследователь
выступит с докладом:
"Арифметики Бюхи и конечные автоматы"
Аннотация:
Арифметикой Бюхи с параметром n >= 2 называется элементарная теория натуральных чисел с равенством, сложением и функцией V_n, возвращающей по натуральному числу k максимальную степень n, на которую k делится. Эти арифметики находят неожиданное применение в теории конечных автоматов: множества, определимые в них, в точности совпадают со множествами, принимаемыми конечным автоматом (автоматом Бюхи) в n-ичной системе счисления. Мы докажем это соответствие и обсудим различные свойства арифметики Бюхи. В частности, мы построим явно нестандартные модели для арифметики Бюхи и докажем, что, в отличие от арифметики Пресбургера, в арифметиках Бюхи интерпретируются линейные порядки, содержащие плотный подпорядок.
Zoom
Идентификатор конференции: 956 6971 8556
При возникновении вопросов пишите по адресу llfp@hse.ru