Automatic Abelian Complexities of Parikh-Collinear Fixed Points
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909212178644992 |
|---|---|
| author | Rigo, Michel Stipulanti, Manon Whiteland, Markus A. |
| author_facet | Rigo, Michel Stipulanti, Manon Whiteland, Markus A. |
| contents | Parikh-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18032 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Automatic Abelian Complexities of Parikh-Collinear Fixed Points Rigo, Michel Stipulanti, Manon Whiteland, Markus A. Discrete Mathematics Formal Languages and Automata Theory Combinatorics Parikh-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. |
| title | Automatic Abelian Complexities of Parikh-Collinear Fixed Points |
| topic | Discrete Mathematics Formal Languages and Automata Theory Combinatorics |
| url | https://arxiv.org/abs/2405.18032 |