A note on the Lie complexity and beyond

DOI10.1016/J.TCS.2023.114343arXiv2207.05859MaRDI QIDQ6138836FDOQ6138836

Authors: Shuo Li 

Publication date: 16 January 2024

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

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.

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)

Cites Work

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

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)