Automatic Abelian Complexities of Parikh-Collinear Fixed Points
Copyright policy )Automatic Abelian Complexities of Parikh-Collinear Fixed Points
AbstractParikh-collinear morphisms have the property that all the Parikh vectors of the images of letters are collinear, i.e., the associated adjacency matrix has rank 1. In the conference DLT–WORDS 2023 we showed that fixed points of Parikh-collinear morphisms are automatic. We also showed that the abelian complexity function of a binary fixed point of such a morphism is automatic under some assumptions. In this note, we fully generalize the latter result. Namely, we show that the abelian complexity function of a fixed point of an arbitrary, possibly erasing, Parikh-collinear morphism is automatic. Furthermore, a deterministic finite automaton with output generating this abelian complexity function is provided by an effective procedure. To that end, we discuss the constant of recognizability of a morphism and the related cutting set.
- Loughborough University United Kingdom
- University of Liège Belgium
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Physique, chimie, mathématiques & sciences de la terre, Abelian complexity, Theory of computing, Computer Science - Formal Languages and Automata Theory, Theoretical Computer Science, Discrete mathematics in relation to computer science, Physical, chemical, mathematical & earth Sciences, Substitution shift, Automated theorem proving, Automatic sequence, FOS: Mathematics, Mathematics - Combinatorics, Complexity functions, Parikh-collinear morphism, Automatic sequences, Sequences and sets, automated theorem proving, substitution shift, Fixed points, Mathématiques, Computational Theory and Mathematics, Morphisms, abelian complexity, recognizable morphism, automatic sequence, Combinatorics (math.CO), Recognizable morphism, Mathematics, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Physique, chimie, mathématiques & sciences de la terre, Abelian complexity, Theory of computing, Computer Science - Formal Languages and Automata Theory, Theoretical Computer Science, Discrete mathematics in relation to computer science, Physical, chemical, mathematical & earth Sciences, Substitution shift, Automated theorem proving, Automatic sequence, FOS: Mathematics, Mathematics - Combinatorics, Complexity functions, Parikh-collinear morphism, Automatic sequences, Sequences and sets, automated theorem proving, substitution shift, Fixed points, Mathématiques, Computational Theory and Mathematics, Morphisms, abelian complexity, recognizable morphism, automatic sequence, Combinatorics (math.CO), Recognizable morphism, Mathematics, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!