Context-free pairs of groups. I: Context-free pairs and graphs

DOI10.1016/J.EJC.2012.03.011zbMATH Open1279.68140arXiv0911.0090OpenAlexW2132847382WikidataQ39822789 ScholiaQ39822789MaRDI QIDQ444402FDOQ444402

Authors: Wolfgang Woess, Tullio Ceccherini-Silberstein 

Publication date: 14 August 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $G$ be a finitely generated group, $A$ a finite set of generators and $K$ a subgroup of $G$. We call the pair $(G,K)$ context-free if the set of all words over $A$ that reduce in $G$ to an element of $K$ is a context-free language. When $K$ is trivial, $G$ itself is called context-free; context-free groups have been classified more than 20 years ago in celebrated work of Muller and Schupp as the virtually free groups. Here, we derive some basic properties of such group pairs. Context-freeness is independent of the choice of the generating set. It is preserved under finite index modifications of $G$ and finite index enlargements of $K$. If $G$ is virtually free and $K$ is finitely generated then $(G,K)$ is context-free. A basic tool is the following: $(G,K)$ is context-free if and only if the Schreier graph of $(G,K)$ with respect to $A$ is a context-free graph.

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

Recommendations

• Context-free pairs of groups. II: Cuts, tree sets, and random walks
• Context-free groups and their structure trees.
• Automorphism groups of context-free graphs
• Context-Free Groups and Bass–Serre Theory
• Groups with context-free conjugacy problems.
• On a subclass of context-free groups
• scientific article; zbMATH DE number 2102749
• Cayley-type graphs for group-subgroup pairs
• Publication:4867142
• Groups of graphs of groups

zbMATH Keywords

graphscontext-free groupcontext-free pairsSchreier graph

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Graph theory (05C99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The accessibility of finitely presented groups
• On torsion-free groups with infinitely many ends
• Title not available (Why is that?)
• Ends of Group Pairs and Non-Positively Curved Cube Complexes
• Ends of pairs of groups
• The theory of ends, pushdown automata, and second-order logic
• The co-word problem for the Higman-Thompson group is context-free
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• Growth and ergodicity of context-free languages
• Groups, the theory of ends, and context-free languages
• Vertex-transitive graphs and accessibility
• On the ends of pairs of groups
• Finiteness Conditions on Subgroups and Formal Language Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Context-free pairs of groups. II: Cuts, tree sets, and random walks
• Automorphism groups of context-free graphs
• Graphs and groups with tree-like properties

Cited In (8)

• Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions
• Groups, the theory of ends, and context-free languages
• Title not available (Why is that?)
• Groups, graphs, languages, automata, games and second-order monadic logic
• Context-free pairs of groups. II: Cuts, tree sets, and random walks
• Formulae and Asymptotics for Coefficients of Algebraic Functions
• The language of self-avoiding walks
• GRAPH PRODUCTS AND CANNON PAIRS

This page was built for publication: Context-free pairs of groups. I: Context-free pairs and graphs

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