Algebraic and context-free subsets of subgroups

DOI10.1016/J.TCS.2023.114229arXiv2210.10001OpenAlexW4387378673MaRDI QIDQ6090487FDOQ6090487

Authors: André Carvalho 

Publication date: 17 November 2023

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On Context-Free Languages
• On Cayley graphs of virtually free groups.
• On the Intersection of Finitely Generated Free Groups
• Groups, the theory of ends, and context-free languages
• Context-Free Groups and Bass–Serre Theory
• On a subclass of context-free groups
• Title not available (Why is that?)
• The submonoid and rational subset membership problems for graph groups.
• On the rational subset problem for groups.
• Rational subsets of groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a kind of Fatou property of context-free groups
• A characterisation of virtually free groups.
• Title not available (Why is that?)
• The generalized conjugacy problem for virtually free 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)