Доклад Александра Запрягаева на семинаре "From the Logical Point of View"

Александр Запрягаев, стажер-исследователь МЛ ЛогЛинФФ, выступил с докладом "Арифметики Бюхи и конечные автоматы"

Арифметикой Бюхи с параметром n >= 2 называется элементарная теория натуральных чисел с равенством, сложением и функцией V_n, возвращающей по натуральному числу k максимальную степень n, на которую k делится. Эти арифметики находят неожиданное применение в теории конечных автоматов: множества, определимые в них, в точности совпадают со множествами, принимаемыми конечным автоматом (автоматом Бюхи) в n-ичной системе счисления. В докладе было доказано это соответствие, а также обсуждались различные свойства арифметики Бюхи. В частности, мы построены явно нестандартные модели для арифметики Бюхи и доказано, что, в отличие от арифметики Пресбургера, в арифметиках Бюхи интерпретируются линейные порядки, содержащие плотный подпорядок.