A note on the Lie complexity and beyond. (English) Zbl 07789588
Summary: In a recent paper, Jason P. Bell and Jeffrey Shallit introduced the notion of Lie complexity and proved that the Lie complexity function of an automatic sequence is automatic. In this note, we give more facts concerning Lie complexity and define the extended Lie complexity and the prefix Lie complexity. Further, we prove that some proprieties of Lie complexity also hold for the extended Lie complexity. Particularly, we prove that the extended Lie complexity function and the first-order difference sequence of the prefix Lie complexity function of an automatic sequence are both automatic. This article is dedicated to Jean-Paul Allouche on the occasion of his 70th birthday.
MSC:
| 68Qxx | Theory of computing |
Software:
WalnutReferences:
| [1] | Allouche, J. P.; Shallit, J., Automatic Sequences: Theory, Applications, Generalizations (2003), Cambridge University Press · Zbl 1086.11015 |
| [2] | Avgustinovich, S. V.; Fon-Der-Flaass, D. G.; Frid, A. E., Arithmetical complexity of infinite words, 51-62 |
| [3] | Bell, J. P.; Shallit, J., Lie complexity of words. Theor. Comput. Sci., 98-108 (2022) · Zbl 1537.68158 |
| [4] | Berge, C., The Theory of Graphs and Its Applications (1982), Greenwood Press · Zbl 0501.05037 |
| [5] | Brlek, S.; Li, S., On the number of squares in a finite word (2022) |
| [6] | Cassaigne, J.; Fici, G.; Sciortino, M.; Zamboni, L. Q., Cyclic complexity of words. J. Comb. Theory, Ser. A, 36-56 (2017) · Zbl 1369.68271 |
| [7] | Charlier, É.; Rampersad, N.; Shallit, J., Enumeration and decidable properties of automatic sequences, 165-179 · Zbl 1221.68122 |
| [8] | De Luca, A.; Fici, G., On the Lie complexity of Sturmian words. Theor. Comput. Sci., 81-85 (2022) · Zbl 1520.68130 |
| [9] | Karhumäki, J., Generalized Parikh mappings and homomorphisms. Inf. Control, 3, 155-165 (1980) · Zbl 0457.68079 |
| [10] | Lempel, A.; Ziv, J., On the complexity of finite sequences. IEEE Trans. Inf. Theory, 1, 75-81 (1976) · Zbl 0337.94013 |
| [11] | Mousavi, H., Automatic theorem proving in Walnut (2016) |
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.
