Suffix-connected languages. (English) Zbl 1535.20159
Summary: Inspired by a series of papers initiated in 2015 by V. Berthé et al. [Monatsh. Math. 176, No. 4, 521–550 (2015; Zbl 1309.68160)], 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.
MSC:
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 20E05 | Free nonabelian groups |
| 68Q45 | Formal languages and automata |
Citations:
Zbl 1309.68160References:
| [1] | Berthé, V.; De Felice, C.; Dolce, F.; Leroy, J.; Perrin, D.; Reutenauer, C.; Rindone, G., Acyclic, connected and tree sets, Monatshefte Math., 176, 4, 521-550 (2015) · Zbl 1309.68160 |
| [2] | Berthé, V.; De Felice, C.; Delecroix, V.; Dolce, F.; Leroy, J.; Perrin, D.; Reutenauer, C.; Rindone, G., Specular sets, Theor. Comput. Sci., 684, 3-28 (2017) · Zbl 1383.68066 |
| [3] | Dolce, F.; Perrin, D., Neutral and tree sets of arbitrary characteristic, Theor. Comput. Sci., 658, 159-174 (2017) · Zbl 1355.68214 |
| [4] | Dolce, F.; Perrin, D., Eventually dendric shift spaces, Ergod. Theory Dyn. Syst., 41, 7, 2023-2048 (2020) · Zbl 1470.37023 |
| [5] | Fogg, N. P., Substitutions in Dynamics, Arithmetics and Combinatorics (2002), Springer Berlin Heidelberg · Zbl 1014.11015 |
| [6] | Almeida, J.; Costa, A., A geometric interpretation of the Schützenberger group of a minimal subshift, Ark. Mat., 54, 2, 243-275 (2016) · Zbl 1394.20033 |
| [7] | Durand, F., A characterization of substitutive sequences using return words, Discrete Math., 179, 1-3, 89-101 (1998) · Zbl 0895.68087 |
| [8] | Steinberg, B., Fundamental groups, inverse Schützenberger automata, and monoid presentations, Commun. Algebra, 28, 11, 5235-5253 (2000) · Zbl 0982.20052 |
| [9] | Kapovich, I.; Myasnikov, A., Stallings foldings and subgroups of free groups, J. Algebra, 248, 2, 608-668 (2002) · Zbl 1001.20015 |
| [10] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan: Macmillan London · Zbl 1226.05083 |
| [11] | Balchin, S.; Rust, D., Computations for symbolic substitutions, J. Integer Seq., 20 (2017) · Zbl 1360.37036 |
| [12] | The Sage Developers, SageMath, the Sage Mathematics Software System, Version 9.2 (2020) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
