Effective MC-finiteness
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913691081900032 |
|---|---|
| author | Filmus, Yuval Fischer, Eldar Makowsky, Johann A. |
| author_facet | Filmus, Yuval Fischer, Eldar Makowsky, Johann A. |
| contents | An integer sequence $(a_n)_{n \in \mathbb{N}}$ is \emph{MC-finite} if for all $m$, the sequence $a_n \bmod m$ is eventually periodic. There are MC-finite sequences $(a_n)_{n \in \mathbb{N}}$ such that the function $F: (m,n) \mapsto a_n \bmod m$ is not computable. In \cite{filmus2023mc} we presented concrete examples of MC-finite sequences taken from the Online Encyclopedia of Integer Sequences (OEIS) without discussing the computability of $F$. In this paper we discuss cases when this $F$ is effectively computable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_10212 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Effective MC-finiteness Filmus, Yuval Fischer, Eldar Makowsky, Johann A. Combinatorics 05, 05C30 An integer sequence $(a_n)_{n \in \mathbb{N}}$ is \emph{MC-finite} if for all $m$, the sequence $a_n \bmod m$ is eventually periodic. There are MC-finite sequences $(a_n)_{n \in \mathbb{N}}$ such that the function $F: (m,n) \mapsto a_n \bmod m$ is not computable. In \cite{filmus2023mc} we presented concrete examples of MC-finite sequences taken from the Online Encyclopedia of Integer Sequences (OEIS) without discussing the computability of $F$. In this paper we discuss cases when this $F$ is effectively computable. |
| title | Effective MC-finiteness |
| topic | Combinatorics 05, 05C30 |
| url | https://arxiv.org/abs/2502.10212 |