Algebraic and context-free subsets of subgroups

DOI10.1016/J.TCS.2023.114229MaRDI QIDQ6090487zbMATH OpenOpenAlexFDO

Authors André Carvalho

Publication date 17 November 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2210.10001

zbMATH Keywords

Fatou propertyvirtually free groupsalgebraic subsetssubsets of groupscontext-free subsets

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We study the relation between the structure of algebraic and context-free subsets of a group G and that of a finite index subgroup H. Using these results, we prove that a kind of Fatou property, previously studied by Berstel and Sakarovitch in the context of rational subsets and by Herbst in the context of algebraic subsets, holds for context-free subsets if and only if the group is virtually free. We also exhibit a counterexample to a question of Herbst concerning this property for algebraic subsets.

Cites work

• scientific article; zbMATH DE number 1820023 (Why is no real title available?)
• scientific article; zbMATH DE number 4047162 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3504469 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 4003555 (Why is no real title available?)
• A characterisation of virtually free groups.
• Context-Free Groups and Bass–Serre Theory
• Groups, the theory of ends, and context-free languages
• On Cayley graphs of virtually free groups.
• On Context-Free Languages
• On a kind of Fatou property of context-free groups
• On a subclass of context-free groups
• On the Intersection of Finitely Generated Free Groups
• On the rational subset problem for groups.
• Rational subsets of groups
• The generalized conjugacy problem for virtually free groups.
• The submonoid and rational subset membership problems for graph groups.

This page was built for publication: Algebraic and context-free subsets of subgroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6090487)