Home

А. Охотин: "Уравнения над множествами целых чисел"

Понедельник, 12 октября, комната 203. Начало в 12:00.

Докладчик: Александр Охотин (университет Турку, Финляндия).

Тема: Уравнения над множествами целых чисел.

Abstract

Доклад посвящён системам уравнений вида $ X=Y+Z $ и $ X=const $, где неизвестные --- множества целых чисел, постоянные --- периодические множества, а сумма двух множеств определяется как $ S+T=\{m+n \mid m \in S, n \in T\} $. Если ограничиваться неотрицательными числами, то такие уравнения представляют собой предельно простой случай языковых уравнений, изучаемых в теории формальных языков; если допускать также и отрицательные числа, получаются языки над свободной группой. На первый взгляд, подобные уравнения --- это тривиальный арифметический объект, и их единственные решения должны быть лишь периодическими. Однако, как было установлено совсем недавно, выразительная мощность подобных систем на самом деле исключительно высока и может быть раскрыта методами теоретической информатики. В докладе будет рассказан путь исследований от первых примеров непериодических решений до описания класса представимых множеств.
Большинство результатов получено докладчиком в соавторстве с Артуром Йежем (Вроцлавский университет, Польша), а последний шаг --- совместно с Томми Лентиненом (университет Турку, Финляндия).