2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Возможно периодические последовательности и их детекция
Сообщение22.08.2023, 20:21 
Сейчас занимаюсь автоматами на строках/массивах, по типу SubstitutionSystem и SequenceReplace Mathematica.
На выходе часто встречаются кандидаты на almost periodic, аналоги Tue-Morse.
Иногда попадаются eventually ("в конечном итоге") periodic. И вот их хотелось бы как-то отбирать, детектировать.
Но разумеется, все мои последовательности конечны. Доказательство того, что вся Tue-Morse almost periodic нетривиально,
я занимаюсь только численными экспериментами.

Читал разные материалы на эту тему. В результате пришел к такому наивному определению.
Возможно периодической в конечном итоге последовательностью назовем конечную группу паттернов:
$$\mathbb{HPP…T}$$
где:
$\mathbb{H}$ - (Head) префикс любого вида, возможно пустой, возможно периодический и т.д.
$\mathbb{P}$ - паттерн, который повторяется после $\mathbb{H}$ минимум два раза
$\mathbb{T}$ - (Tail) суффикс, любой префикс $\mathbb{P}$, то есть предполагаемое начало следующего периода

Буду признателен за любые комментарии на это определение!
Но в любом случае, похоже оно не глупое. Поэтому я начал пытаться его детектировать.
Единственный разумный вариант (опять же после чтения сабжа) - использование Z-функции или префикс-функции.
Уверен, что именно они помогут в детектировании искомого паттерна,
но как-то не складывается в голове, как это оформить четко и эффективно.

 
 
 
 Re: Возможно периодические последовательности и их детекция
Сообщение28.09.2023, 14:45 
Аватара пользователя
С этой задачей должен справляться Walnut: https://cs.uwaterloo.ca/~shallit/walnut.html

 
 
 
 Re: Возможно периодические последовательности и их детекция
Сообщение28.09.2023, 15:36 
Аватара пользователя
Несложно заметить, что если потребовать, чтобы паттерн повторялся ровно 2 раза, то определение не поменяется (лишние вхождения можно включить в префикс).

Разверните строку и посчитайте значение префикс-функции в точке $|T| + 2\cdot |P|$ (для случая периодических строк). Подумайте, как просто по этому значению (и еще одному числу) понять, что данная точка может рассматриваться как начало периода.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group