Эта публикация цитируется в
3 статьях
Конечная порождаемость некоторых групп рекурсивных перестановок
С. А. Волков
Аннотация:
Пусть класс
$\mathcal Q$ функций натурального аргумента замкнут относительно суперпозиции и содержит тождественную функцию. Множество перестановок
$f$ таких, что
$f,f^{-1}\in\mathcal Q$, образует группу (относительно операции композиции), которую будем обозначать
$Gr(\mathcal Q)$. В работе доказана конечная порождаемость
$Gr(\mathcal Q)$ для большого семейства классов
$\mathcal Q$, удовлетворяющих определенным требованиям. В качестве примера рассмотрен класс
$\mathrm{FP}$ функций, вычислимых за полиномиальное время на машине Тьюринга. Полученный результат обобщается на классы
$\mathscr E^n$ иерархии Гжегорчика,
$n\geq2$.
Кроме того, для рассматриваемых классов
$\mathcal Q$ определено минимальное число перестановок, порождающих группу
$Gr(\mathcal Q)$, равное двум. Точнее, получен более сильный результат: существуют две перестановки из данной группы, композициями которых можно получить любую перестановку этой группы.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 06–01–00438.
УДК:
519.7 Статья поступила: 22.06.2007
DOI:
10.4213/dm1026