Geodesic
On asymptotically automatic sequences
Jakub Konieczny 1
1 Université Claude Bernard Lyon 1 CNRS UMR 5208 Institut Camille Jordan F-69622 Villeurbanne Cedex, France and Department of Computer Science University of Oxford Oxford OX1 3QD, UK
Acta Arithmetica, Tome 215 (2024) no. 3, pp. 249-287 Cet article a éte moissonné depuis la source Institute of Mathematics Polish Academy of Sciences

Voir la notice de l'article

We study the notion of an asymptotically automatic sequence, which generalises the notion of an automatic sequence. While $k$-automatic sequences are characterised by finiteness of $k$-kernels, the $k$-kernels of asymptotically $k$-automatic sequences are only required to be finite up to equality almost everywhere. We prove basic closure properties and a linear bound on asymptotic subword complexity, show that results concerning frequencies of symbols are no longer true for the asymptotic analogue, and discuss some classification problems. Published in Open Access (under CC-BY license).
DOI : 10.4064/aa230619-26-4
Keywords: study notion asymptotically automatic sequence which generalises notion automatic sequence while k automatic sequences characterised finiteness k kernels k kernels asymptotically k automatic sequences only required finite equality almost everywhere prove basic closure properties linear bound asymptotic subword complexity results concerning frequencies symbols longer asymptotic analogue discuss classification problems

Jakub Konieczny  1

1 Université Claude Bernard Lyon 1 CNRS UMR 5208 Institut Camille Jordan F-69622 Villeurbanne Cedex, France and Department of Computer Science University of Oxford Oxford OX1 3QD, UK 
@article{10_4064_aa230619_26_4,
     author = {Jakub Konieczny},
     title = {On asymptotically automatic sequences},
     journal = {Acta Arithmetica},
     pages = {249--287},
     year = {2024},
     volume = {215},
     number = {3},
     doi = {10.4064/aa230619-26-4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/aa230619-26-4/}
}
TY  - JOUR
AU  - Jakub Konieczny
TI  - On asymptotically automatic sequences
JO  - Acta Arithmetica
PY  - 2024
SP  - 249
EP  - 287
VL  - 215
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4064/aa230619-26-4/
DO  - 10.4064/aa230619-26-4
LA  - en
ID  - 10_4064_aa230619_26_4
ER  - 
%0 Journal Article
%A Jakub Konieczny
%T On asymptotically automatic sequences
%J Acta Arithmetica
%D 2024
%P 249-287
%V 215
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4064/aa230619-26-4/
%R 10.4064/aa230619-26-4
%G en
%F 10_4064_aa230619_26_4
Jakub Konieczny. On asymptotically automatic sequences. Acta Arithmetica, Tome 215 (2024) no. 3, pp. 249-287. doi: 10.4064/aa230619-26-4

Cité par Sources :