Suffix-connected languages
From MaRDI portal
Publication:6369126
DOI10.1016/J.TCS.2022.05.001arXiv2106.00452MaRDI QIDQ6369126
Publication date: 1 June 2021
Abstract: Inspired by a series of papers initiated in 2015 by Berth'e et al., we introduce a new condition called suffix-connectedness. We show that the groups generated by the return sets of a uniformly recurrent suffix-connected language lie in a single conjugacy class of subgroups of the free group. Moreover, the rank of the subgroups in this conjugacy class only depends on the number of connected components in the extension graph of the empty word. We also show how to explicitly compute a representative of this conjugacy class using the first order Rauzy graph. Finally, we provide an example of suffix-connected, uniformly recurrent language that contains infinitely many disconnected words.
Formal languages and automata (68Q45) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
This page was built for publication: Suffix-connected languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6369126)
