Starting from context-free inverse graphs, we introduce a new class of groups and study their structural properties. We establish closure properties, show that their coword problems are context-free, analyze torsion elements, and realize them as subgroups of the asynchronous rational group. Context-freeness is preserved under a generalized free product of graphs, and using this construction, we provide examples of groups that are not residually finite or not polycontext-free, making them relevant for testing the Lehnert and Brough conjectures. Moreover, we investigate how small local modifications of a graph affect the global structure of the transition group, showing that for locally quasi-transitive graphs with infinite orbits, the transition group decomposes into a highly structured quotient by a bounded torsion subgroup, showing strong global constraints induced by local graph properties.

D'Angeli, D., Matucci, F., Perego, D., Rodaro, E. (2026). Context-free graphs and their transition groups. TRANSACTIONS OF THE LONDON MATHEMATICAL SOCIETY, 13(1 (December 2026)) [10.1112/tlm3.70034].

Context-free graphs and their transition groups

Matucci, F
Co-primo
;
2026

Abstract

Starting from context-free inverse graphs, we introduce a new class of groups and study their structural properties. We establish closure properties, show that their coword problems are context-free, analyze torsion elements, and realize them as subgroups of the asynchronous rational group. Context-freeness is preserved under a generalized free product of graphs, and using this construction, we provide examples of groups that are not residually finite or not polycontext-free, making them relevant for testing the Lehnert and Brough conjectures. Moreover, we investigate how small local modifications of a graph affect the global structure of the transition group, showing that for locally quasi-transitive graphs with infinite orbits, the transition group decomposes into a highly structured quotient by a bounded torsion subgroup, showing strong global constraints induced by local graph properties.
Articolo in rivista - Articolo scientifico
Context free graphs, Chomsky hierarchy, transition groups
English
6-lug-2026
2026
13
1 (December 2026)
e70034
open
D'Angeli, D., Matucci, F., Perego, D., Rodaro, E. (2026). Context-free graphs and their transition groups. TRANSACTIONS OF THE LONDON MATHEMATICAL SOCIETY, 13(1 (December 2026)) [10.1112/tlm3.70034].
File in questo prodotto:
File Dimensione Formato  
D’Angeli et al-2026-Transactions of the London Mathematical Society-VoR.pdf

accesso aperto

Descrizione: Online first
Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Licenza: Creative Commons
Dimensione 2.48 MB
Formato Adobe PDF
2.48 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/630445
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
Social impact