2025/02/20 by Carvalho, André, Nyberg-Brodda, Carl-Fredrik · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR)
paper · doi:10.48550/arxiv.2502.14329
We study subsets of groups and monoids defined by language-theoretic means, generalizing the classical approach to the word problem. We expand on results by Herbst from 1991 to a more general setting, and for a class of languages C we define the classes of C^∀-flat and C^∃-flat groups. We prove several closure results for these classes of groups, prove a connection with the word problem, and characterize C^∀-flat groups for several classes of languages. In general, we prove that the class of C^∀-flat groups is a strict subclass of the class of groups with word problem in C, including for the class REC of recursive languages, for which C^∀-flatness for a group resp. monoid is proved to be equivalent to the decidability of the subgroup membership problem resp. the submonoid membership problem. We provide a number of examples, including the Tarski monsters of Ol'shanskii, showing the difficulty of characterizing C^∃-flat groups. As an application of our general methods, we also prove in passing that if C is a full semi-AFL, then the class of epi-C groups is closed under taking finite index subgroups. This answers a question recently posed by Al Kohli, Bleak & Elliott.