A note on the Lie complexity and beyond

DOI10.1016/J.TCS.2023.114343MaRDI QIDQ6138836zbMATH OpenFDO

Authors Shuo Li

Publication date 16 January 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

automatic sequenceRauzy graphLie complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: In a recent paper, Jason P. Bell and Jeffrey Shallit introduced the notion of {em 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.

Cites work

• Automatic Sequences
• Cyclic complexity of words
• Enumeration and decidable properties of automatic sequences
• Generalized Parikh mappings and homomorphisms
• Lie complexity of words
• On the Complexity of Finite Sequences
• On the Lie complexity of Sturmian words
• k-optimal partitions of a directed graph

This page was built for publication: A note on the Lie complexity and beyond

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