Языки сопряженности и рост сопряженности относительно подмножеств групп

Основная информация

• ID статьи: 2510.20923
• Название: Conjugacy languages and conjugacy growth relative to subsets of groups
• Авторы: André Carvalho (Университет Порто), Ana-Catarina C. Monteiro (NOVA FCT)
• Классификация: math.GR (Теория групп)
• Дата подачи: 23 октября 2025 г.
• Ссылка на статью: https://arxiv.org/abs/2510.20923

Аннотация

В данной работе исследуются языки сопряженности (conjugacy languages) в теории групп, в частности обобщенная проблема сопряженности (generalized conjugacy problem). Основной вопрос заключается в следующем: для заданного элемента группы $g \in G$ и подмножества $U \subset G$ определить, существует ли в $U$ элемент, сопряженный с $g$ (возможно с ограничениями на сопрягающий элемент). Авторы определяют соответствующие языки $\text{ConjGeo}(U,V)$, $\text{CycGeo}(U)$, $\text{ConjSL}(U)$ и $\text{ConjMinLenSL}(U,V)$ и доказывают результаты о регулярности для нескольких классов групп: для свободных групп при рациональных подмножествах $U, V$ эти языки регулярны; для гиперболических групп результаты справедливы, когда $U$ представимо регулярным геодезическим языком; соответствующие результаты получены также для виртуально циклических и виртуально абелевых групп. Кроме того, авторы определяют функции относительного роста сопряженности и демонстрируют, что их поведение сильно зависит от выбора подмножества.

Исследовательский контекст и мотивация

Предпосылки проблемы

1. Классическая проблема сопряженности: Одна из фундаментальных проблем в теории групп — проблема сопряженности (CP), то есть определение того, сопряжены ли два элемента группы. Это может быть обобщено до обобщенной проблемы сопряженности (GCP): для заданного элемента $g$ и подмножества $U$ определить, имеет ли $g$ сопряженный элемент в $U$.
2. Пересечение формальных языков и теории групп: Теория формальных языков предоставляет мощные инструменты для исследования проблем теории групп. Например, теорема Анисимова утверждает, что конечные группы — это в точности группы, у которых словесная проблема является регулярным языком; теорема Миллера-Шуппа характеризует виртуально свободные группы как группы, у которых словесная проблема является контекстно-свободным языком.
3. Ограничения предыдущих работ:
   • Чобану и др. 12 исследовали языки сопряженности при $U = V = G$
   • Ладра и Сильва 23 доказали разрешимость обобщенной проблемы сопряженности для виртуально свободных групп
   • Карвалью и Сильва 10 изучали двойную обобщенную проблему сопряженности для рациональных подмножеств
   • Однако систематическое исследование свойств языков сопряженности для общих подмножеств $U \subset G$ отсутствовало

Мотивация исследования

1. Теоретическая полнота: Обобщение от $U = G$ к общим подмножествам $U$ и построение более полной теоретической базы
2. Проблемы разрешимости: Установление результатов разрешимости через свойства языков (такие как регулярность)
3. Поведение функций роста: Функции относительного роста сопряженности могут проявлять поведение, совершенно отличное от классического роста сопряженности
4. Единый подход к различным классам групп: Предоставление единой теоретико-языковой базы для свободных групп, гиперболических групп, виртуально циклических групп, виртуально абелевых групп и других

Основные вклады

1. Определение языков относительной сопряженности: Для подмножеств $U, V \subseteq G$ систематически определены языки:
   • $\text{ConjGeo}(U,V)$: язык кратчайших представителей сопряженности (с ограничениями)
   • $\text{CycGeo}(U)$: язык циклических геодезических слов
   • $\text{ConjSL}(U)$: язык стандартной формы короткого лексикографического порядка сопряженности
   • $\text{ConjMinLenSL}(U,V)$: язык минимальной длины короткого лексикографического порядка
2. Результаты регулярности для свободных групп (Теорема 4.5): Для свободной группы $F_X$ и рациональных подмножеств $U, V$ доказано, что $\text{ConjGeo}(U,V)$ и $\text{ConjMinLenSL}(U,V)$ являются регулярными языками
3. Результаты регулярности для гиперболических групп (Теорема 5.8): Для $\delta$-гиперболической группы, если $L$ — регулярный геодезический язык, то $\text{ConjGeo}(L\pi)$ и $\text{ConjMinLenSL}(L\pi)$ регулярны
4. Полная характеризация виртуально циклических групп (Теорема 6.1): Для виртуально циклической группы и любого рационального подмножества $U$ язык $\text{ConjSL}(U)$ регулярен
5. Сохранение класса языков для виртуально абелевых групп (Теоремы 7.3, 7.4): При надлежащих условиях $\text{ConjGeo}(U)$ сохраняет свойства исходного класса языков
6. Многообразие относительного роста сопряженности (Теорема 3.1): Построены рациональные подмножества $U_d$ такие, что относительный кумулятивный рост сопряженности $cc_{F_2,X,U_d}(n)$ является полиномом порядка от $n^{d-1}$ до $n^d$, что демонстрирует значительное отличие от классического экспоненциального роста
7. Связь с разрешимостью (Предложение 3.2): Установлена связь между регулярностью языков сопряженности и разрешимостью обобщенной проблемы сопряженности

Подробное описание методов

Определение задачи

Основная проблема: Обобщенная проблема сопряженности (с ограничениями)

• Входные данные: элемент группы $g \in G$, подмножества $U, V \subseteq G$
• Проблема: Существуют ли $u \in U$ и $v \in V$ такие, что $g = v^{-1}uv$?
• Частный случай: При $V = G$ сводится к стандартной обобщенной проблеме сопряженности

Ключевое определение: $\alpha(K,L) = \bigcup_{u \in L} u^{-1}Ku$

Это обозначает объединение элементов из $K$, сопряженных элементами из $L$.

Определение основных языков

Для подмножеств $U, V \subseteq G$ и порождающего множества $X$:

1. $\text{ConjGeo}_X(U,V)$: $\text{ConjGeo}_X(U,V) = \text{ConjGeo}_X(G) \cap \alpha(U,V)\pi^{-1}$ представляет кратчайшие представительные слова каждого класса сопряженности в $\alpha(U,V)$
2. $\text{CycGeo}_X(U)$: $\text{CycGeo}_X(U) = \{w \in \text{Geo}_X(U) \mid w \text{ — циклическое геодезическое слово}\}$
3. $\text{ConjMinLenSL}_X(U,V)$: $\text{ConjMinLenSL}_X(U,V) = \{w_g \in \text{Geo}_X(\alpha(U,V)) \mid |g| = |g|_c\}$ где $w_g$ — стандартная форма короткого лексикографического порядка элемента $g$, $|g|_c$ — минимальная длина в классе сопряженности
4. $\text{ConjSL}_X(U)$: $\text{ConjSL}_X(U) = \{z_c \in \text{Geo}_X(\alpha(U)) \mid c \text{ — класс сопряженности}\}$ стандартная форма короткого лексикографического порядка для каждого класса сопряженности, пересекающегося с $U$

Технические инновации

1. Техника языков перестановок для свободных групп (Permutation Language)

Определение 4.2: Для регулярных языков $K, L$ определяется язык перестановок $P_{K,L} = \{u\ell \mid \ell \in L, \ell u \in K\}$

Ключевая лемма (Предложение 4.3): Когда $UV$ редуцирован (reduced), то есть $|k\ell| \geq |k|$ для всех $k \in U, \ell \in V$, то $\text{ConjGeo}(U,V) = \text{ConjGeo}(F_X) \cap P_{U,V}$

Схема доказательства:

• Использование минимального автомата $A = (Q, q_0, T, E)$ для распознавания $U$
• Доказательство того, что $P_{U,V} = \bigcup_{p \in Q, t \in T} L_{p,t}(L_{q_0,p} \cap V)$
• Ключевое наблюдение: в свободной группе $UV$ редуцирован тогда и только тогда, когда $\ell$ является префиксом $k$ эквивалентно $|k\ell| = |k|$

2. Техника квазигеодезических для гиперболических групп

Леммы 5.1-5.3: Использование свойства тонких треугольников гиперболических групп:

• Лемма 5.1: Отношения сопряженности полностью редуцированных слов могут быть реализованы короткими сопрягающими элементами (длины $\leq 2\delta + 1$)
• Лемма 5.2: Обобщенная версия квазигеодезических слов
• Лемма 5.3: Регулярные геодезические языки допускают построение квазиредуцированных представительных языков

Предложение 5.5: $(1,r)$-квазигеодезические и $(1,s)$-квазигеодезические удовлетворяют свойству ограниченного асинхронного сопровождения (boundedly asynchronous fellow travel property) с константой расстояния $N$, зависящей от $r, s, \delta$

Следствие 5.6: $(1,\epsilon)$-квазигеодезические языки образуют двойной автоматический структуру

Основная техника (Лемма 5.7): Для регулярного геодезического языка $K$, $\text{CycGeo}(\alpha(K\pi)) = S \cup \left[\text{CycGeo}(G) \cap \bigcup_{|z| \leq 2(\delta+\gamma)} \text{Cyc}(L_2(z))\right]$ где $S$ — конечный язык, $L_2(z)$ определяется автоматом отношения сопряженности

3. Техника автоморфизмов для виртуально абелевых групп

Ключевое наблюдение (Лемма 7.2): Для абелевой группы $G$ и автоморфизма $\phi$, $\phi(\text{Geo}_X(U)) = \text{Geo}_{\phi(X)}(\phi(U))$

Стратегия доказательства Теоремы 7.4:

• Пусть $N$ — абелева нормальная подгруппа конечного индекса, $T = \{b_1, \ldots, b_n\}$ — представители смежных классов
• Каждый $t \in T$ определяет автоморфизм сопряженности $\alpha_t: n \mapsto t^{-1}nt$
• Для $U = \bigcup_{i=1}^n U_i b_i$ (где $U_i \in C_\bullet(N)$) вычисляется $\alpha(U_i b_i) = \bigcup_{s \in T} [U_i N(Q_{b_i}^{-1} - I)]^{Q_s} \cdot s^{-1}b_i s$ где $Q_t$ — матричное представление $\alpha_t$
• Использование замкнутости full semi-AFL для доказательства $\alpha(U_i b_i) \in C_\bullet(G)$

Экспериментальная установка

Примечание: Данная работа — чистая теоретическая математическая статья, не содержащая экспериментальной части. Все результаты являются строгими математическими доказательствами.

Конструктивные примеры

Конструкция Теоремы 3.1:

• Использование конструкции Рига 26: для каждого $d \in \mathbb{N}$ существует регулярный язык $L_d$ такой, что число слов длины $n$ равно $n^d$
• Алфавит $\Sigma_d = \{a_1, \ldots, a_{u_d}\}$, каждый $a_i$ заменяется на $a^i b^i$
• Получение языка $K_d \subseteq \{a,b\}^*$, элементы которого свободно независимы в свободной группе
• Анализ: $\frac{\sum_{i=0}^{\lfloor n/(2u_d) \rfloor} 2i^d}{i-2} < cc_{F_2,X,U_d}(n) < \sum_{i=0}^{\lfloor n/2 \rfloor} i^d$ дает $n^{d-1} \lesssim cc_{F_2,X,U_d}(n) \lesssim n^d$

Экспериментальные результаты

Основные теоретические результаты

1. Свободные группы (Теорема 4.5)

Результат: Для свободной группы $F_X$ и рациональных подмножеств $U, V$,

• $\text{ConjGeo}(U,V)$ — регулярный язык
• $\text{ConjMinLenSL}(U,V)$ — регулярный язык

Ключевые моменты доказательства:

• Использование разложения Карвалью-Сильва 10: $\alpha(U,V) = \bigcup_{a \in \tilde{X}} (Y_a \cup Z_a)$
• Применение техники языков перестановок к каждой компоненте
• Использование регулярности $\text{ConjGeo}(F_X)$

Значение: Улучшение результата 10 от контекстно-свободных языков к регулярным

2. Гиперболические группы (Теорема 5.8)

Результат: Для $\delta$-гиперболической группы $G$ и регулярного геодезического языка $L$,

• $\text{ConjGeo}(L\pi)$ регулярен
• $\text{ConjMinLenSL}(L\pi)$ регулярен

Структура доказательства: $\text{ConjGeo}(L\pi) = S \cup \left[\left(\text{CycGeo}(\alpha(L\pi)) \cap \bigcup_{k \geq 8\delta+1} X^k\right) \setminus \text{Cyc}\left(\bigcup_{|\alpha| \leq 2\delta+1} L(\alpha)\right)\right]$

Следствие 5.9: Обобщенная проблема сопряженности для виртуально свободных групп разрешима (предоставляет новое доказательство на основе теории языков)

3. Виртуально циклические группы (Теорема 6.1)

Результат: Для виртуально циклической группы $G$ и рационального подмножества $U$ язык $\text{ConjSL}(U)$ регулярен

Ключевые моменты доказательства:

• Разложение $\text{ConjSL}(U) = (\text{ConjSL}(U) \cap C\pi^{-1}) \cup (\text{ConjSL}(U) \cap (G \setminus C)\pi^{-1})$
• где $C$ — централизатор $H \cong \mathbb{Z}$
• Второе слагаемое конечно (так как $G \setminus C$ содержит только конечное число классов сопряженности)
• Первое слагаемое получается через регулярность $\text{CycGeo}(\alpha(U))$ и теоретико-множественные операции

4. Виртуально абелевы группы (Теоремы 7.3, 7.4)

Теорема 7.3: Пусть $G$ — виртуально абелева группа, $N$ — абелева нормальная подгруппа конечного индекса, $U \subseteq N$. Если $C$ замкнута относительно конечных объединений и регулярных пересечений, и $\text{Geo}_Z(U) \in C$, то существует порождающее множество $Z$ такое, что

• $\text{ConjGeo}_Z(U) \in C$
• $\text{ConjMinLenSL}_Z(U) \in C$

Теорема 7.4: Если $C$ — full semi-AFL и $U \in C_\bullet(G)$, то $\alpha(U) \in C_\bullet(G)$

Следствие 7.5: Если $K \in C_\forall(G)$, то $\text{ConjGeo}(K) \in C$

Результаты функций роста (Теорема 3.1)

Конструкция: Для каждого $d \in \mathbb{N}$ существует рациональное подмножество $U_d \in \text{Rat}(F_2)$ такое, что $n^{d-1} \lesssim cc_{F_2,X,U_d}(n) \lesssim n^d$

Сравнение: Классический кумулятивный рост сопряженности $cc_{F_2,X}(n)$ экспоненциален

Значение:

1. Демонстрирует, что относительный рост может быть полиномом произвольной степени
2. Показывает, что выбор подмножества оказывает фундаментальное влияние на поведение роста
3. Предоставляет количественную перспективу на сложность обобщенной проблемы сопряженности

Результаты разрешимости (Предложение 3.2)

Теорема: Пусть $C$ — класс подмножеств, $L$ — класс языков. Если выполнены условия:

1. $U, V \in C \Rightarrow \text{ConjGeo}(U,V) \in L$ вычислим
2. $U \in C, g \in G \Rightarrow U^g \in C$ вычислим
3. $G$ имеет разрешимую проблему сопряженности
4. $L$ имеет разрешимую проблему принадлежности

то $G$ имеет разрешимую $C$-обобщенную проблему сопряженности (с $C$-ограничениями)

Применение: Объединение с результатами регулярности для различных классов групп непосредственно дает разрешимость

Связанные работы

Исследования языков сопряженности в теории групп

1. Холт-Рис-Ровер 22:
   • Определение проблемы сопряженности как множества пар $(u,v)$
   • Доказательство того, что проблема сопряженности для виртуально свободных групп асинхронно индексирована
   • Виртуально циклические группы — это в точности группы, у которых проблема сопряженности асинхронно контекстно-свободна
2. Левин 24:
   • Виртуально свободные группы — это в точности группы, у которых каждый класс сопряженности является контекстно-свободным подмножеством
   • Обобщение теоремы Миллера-Шуппа
3. Чобану-Хермиллер-Холт-Рис 12:
   • Определение языков $\text{ConjGeo}(G)$, $\text{ConjMinLenSL}(G)$, $\text{ConjSL}(G)$ и др.
   • Доказательство регулярности $\text{ConjGeo}(G)$ и $\text{ConjMinLenSL}(G)$ для гиперболических групп
   • Язык $\text{ConjGeo}(G)$ для виртуально абелевых групп кусочно-измерим
   • Язык $\text{ConjSL}(G)$ для виртуально циклических групп регулярен

Исследования обобщенной проблемы сопряженности

4. Ладра-Сильва 23:
   • Доказательство разрешимости обобщенной проблемы сопряженности с рациональными ограничениями для виртуально свободных групп
   • Метод: построение языков сопрягающих элементов и доказательство их регулярности
5. Карвалью-Сильва 10:
   • Исследование двойной обобщенной проблемы сопряженности
   • Доказательство того, что для виртуально свободных групп и рациональных подмножеств $U, V$ язык $\alpha(U,V)\pi^{-1}$ контекстно-свободен
   • Введение концепции представления через геодезические языки
6. Дикерт-Гутьеррес-Хагенах 16:
   • Экзистенциальная теория в свободных группах с рациональными ограничениями PSPACE-полна

Теория автоматических групп

7. Эпштейн и др. 17:
   • Основная теория автоматических и двойных автоматических групп
   • Регулярность стандартных форм короткого лексикографического порядка
8. Хербст 19, Карвалью-Найберг-Бродда 9:
   • Систематическое исследование языковых подмножеств
   • Свойства обозначений $C_\bullet(G)$ и понятий cone, full semi-AFL

Продвижение в данной работе

• От $U = G$ к общим подмножествам: Систематическое обобщение существующих результатов
• Единая база: Предоставление единого языково-теоретического подхода для нескольких классов групп
• Более сильные результаты: Улучшение результатов для свободных групп от контекстно-свободных к регулярным
• Новая перспектива: Функции относительного роста раскрывают важность выбора подмножества

Выводы и обсуждение

Основные выводы

1. Языково-теоретическая характеризация:
   • Свободные группы: языки относительной сопряженности рациональных подмножеств регулярны
   • Гиперболические группы: языки относительной сопряженности геодезически представимых подмножеств регулярны
   • Виртуально циклические группы: языки короткого лексикографического порядка рациональных подмножеств регулярны
   • Виртуально абелевы группы: сохранение свойств класса языков
2. Многообразие функций роста: Относительный рост сопряженности может быть полиномом произвольной степени, что контрастирует с классическим экспоненциальным ростом
3. Разрешимость: Установлена связь между регулярностью языков сопряженности и разрешимостью обобщенной проблемы сопряженности

Ограничения

1. Ограничения для виртуально абелевых групп:
   • Теорема 7.3 требует $U \subseteq N$ (внутри абелевой подгруппы)
   • Общий случай (когда $U$ не в $N$) остается открытым
2. Требования к классам языков:
   • Гиперболические группы требуют регулярного геодезического представления
   • Виртуально абелевы группы требуют $\text{Geo}(U) \in C$
   • Не все рациональные подмножества удовлетворяют этим условиям (например, пример 7.1)
3. Конструктивность:
   • Границы степени роста в Теореме 3.1 не точны (между $n^{d-1}$ и $n^d$)
   • Неизвестно, существуют ли примеры с точной степенью $d$
4. Вычислительная сложность:
   • Доказана разрешимость, но анализ сложности отсутствует
   • Эффективность конструкции автоматов не обсуждается

Направления будущих исследований

Статья явно формулирует две открытые проблемы:

1. Точная степень роста (Проблема 1):
   • Можно ли построить рациональные подмножества $U_d$ такие, что $cc_{F_2,X,U_d}(n) \sim n^d$ точно?
   • В настоящее время имеется только $n^{d-1} \lesssim cc_{F_2,X,U_d}(n) \lesssim n^d$
2. Общий случай для виртуально абелевых групп (Проблема 2):
   • Каковы свойства $\text{ConjGeo}(U)$ при $U \not\subseteq N$?
   • Ключевой технический вопрос: могут ли элементы $\text{ConjGeo}(U)$ содержать подслова из $\text{ConjGeo}(G \setminus \alpha(U))$?
   • Рекомендуется начать с конкретных классов языков (регулярные, кусочно-измеримые, кусочно-исключаемые)
3. Другие потенциальные направления:
   • Анализ вычислительной сложности
   • Обобщение на другие классы групп (CAT(0)-группы, относительно гиперболические группы)
   • Обобщенная проблема сопряженности с несколькими ограничениями
   • Асимптотические свойства функций относительного роста

Глубокая оценка

Преимущества

1. Теоретическая глубина:
   • Систематическое обобщение классических результатов Чобану и др. 12
   • Полная языково-теоретическая характеризация для нескольких важных классов групп
   • Изящные техники доказательства, особенно методы языков перестановок и автоморфизмов
2. Единая база:
   • Обозначение $\alpha(U,V)$ унифицирует различные случаи
   • Обозначение $C_\bullet(G)$ предоставляет гибкий способ работы с классами языков
   • Предложение 3.2 устанавливает общую связь между теорией языков и разрешимостью
3. Технические инновации:
   • Языки перестановок $P_{K,L}$ — новый инструмент для работы со свободными группами
   • Техника квазигеодезических для гиперболических групп обобщает существующие методы
   • Метод матриц автоморфизмов для виртуально абелевых групп оригинален
4. Понимание функций роста:
   • Теорема 3.1 демонстрирует богатство относительного роста
   • Предоставляет количественную перспективу на сложность обобщенной проблемы сопряженности
   • Конструктивный метод имеет общее применение
5. Качество изложения:
   • Четкая структура, постепенное развитие от общего к частному
   • Полные предварительные знания, точные определения
   • Достаточные детали доказательств, строгая логика

Недостатки

1. Ограничения охвата:
   • Результаты для виртуально абелевых групп требуют $U \subseteq N$ или $\text{Geo}(U) \in C$
   • Недостаточная обработка общих рациональных подмножеств (например, пример 7.1)
   • Другие важные классы групп (группы прямоугольных углов, графовые группы) не рассмотрены
2. Точность границ функций роста:
   • Границы в Теореме 3.1 не точны (отличаются на одну степень)
   • Отсутствует конструкция, достигающая точной степени
   • Относительный рост для других классов групп не исследован
3. Вычислительные аспекты:
   • Анализ алгоритмической сложности отсутствует
   • Эффективность конструкции автоматов не обсуждается
   • Практическая вычислимость не проверена
4. Применение:
   • Практические приложения не обсуждаются (криптография, алгоритмическая теория групп)
   • Связь с другими проблемами теории групп слабая
   • Отсутствуют конкретные примеры и вычислительные иллюстрации
5. Открытые проблемы:
   • Общий случай для виртуально абелевых групп — важный пробел
   • Техническая сложность Проблемы 2 не полностью проанализирована
   • Отсутствуют предложения по решению этих проблем

Влияние

1. Теоретический вклад:
   • Важное обобщение теории языков сопряженности
   • Установление глубокой связи между выбором подмножества и свойствами языков
   • Предоставление систематической базы для будущих исследований
2. Методологическая ценность:
   • Техника языков перестановок может применяться к другим проблемам
   • Метод автоморфизмов предоставляет новый инструмент для исследования виртуально абелевых групп
   • Теорема о сохранении класса языков имеет общее значение
3. Воспроизводимость:
   • Подробные доказательства, высокая верифицируемость
   • Явные конструкции
   • Отсутствие вычислительной реализации
4. Направления будущих исследований:
   • Четко сформулированные открытые проблемы с ясными направлениями
   • Предоставление шаблона для исследования других классов групп
   • Возможность вдохновить исследования связанных проблем

Области применения

1. Теоретические исследования:
   • Проблемы принятия решений в комбинаторной теории групп
   • Пересечение формальной теории языков и алгебры
   • Исследование функций роста и асимптотических свойств
2. Алгоритмическая теория групп:
   • Разработка алгоритмов решения обобщенной проблемы сопряженности
   • Оптимизация вычисления представителей классов сопряженности
   • Символические вычисления с рациональными подмножествами
3. Связанные области:
   • Теория автоматических групп
   • Геометрическая теория групп (гиперболические группы, CAT(0)-группы)
   • Теория вычислительной сложности
4. Потенциальные приложения:
   • Криптографические протоколы на основе групп
   • Вычисление фундаментальных групп в топологии
   • Теория автоматов

Ключевые ссылки

12 L. Ciobanu, S. Hermiller, D. Holt, S. Rees. Conjugacy languages in groups. Israel J. Math., 211:311–347, 2016.

• Прямая основа данной работы, определяет языки сопряженности при $U = G$

10 A. Carvalho, P. V. Silva. Geodesic languages for rational subsets and conjugates in virtually free groups. arXiv:2410.20412v2, 2024.

• Доказывает контекстно-свободность $\alpha(U,V)\pi^{-1}$, данная работа улучшает до регулярности

23 M. Ladra, P. V. Silva. The generalized conjugacy problem for virtually free groups. Forum Math., 23:447–482, 2011.

• Классический результат о разрешимости обобщенной проблемы сопряженности для виртуально свободных групп

25 D. E. Muller, P. E. Schupp. Groups, the theory of ends, and context-free languages. J. Comput. System Sci., 26(3):295–310, 1983.

• Теорема Миллера-Шуппа: словесная проблема виртуально свободных групп контекстно-свободна

19 T. Herbst. On a subclass of context-free groups. RAIRO Inform. Théor. Appl., 25:255–272, 1991.

• Словесная проблема виртуально циклических групп — one-counter, введено обозначение $C_\bullet$

9 A. Carvalho, C. F. Nyberg-Brodda. On linguistic subsets of groups and monoids. arXiv:2502.14329, 2025.

• Систематическая теория языковых подмножеств, источник теорем 2.2 и 2.3

Общая оценка: Это высокого качества теоретическая математическая статья, которая систематически обобщает теорию языков сопряженности на случай подмножеств и предоставляет глубокую языково-теоретическую характеризацию для нескольких важных классов групп. Технически содержит инновации (языки перестановок, методы автоморфизмов), теоретически имеет глубину (многообразие функций роста, сохранение класса языков). Основные недостатки — нерешенный общий случай для виртуально абелевых групп и отсутствие анализа вычислительной сложности. Статья предоставляет четкие направления для будущих исследований и, как ожидается, окажет продолжительное влияние на комбинаторную теорию групп и теорию формальных языков.