Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2308.10977 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912295694630912 |
|---|---|
| author | Rowland, Eric Stipulanti, Manon Yassawi, Reem |
| author_facet | Rowland, Eric Stipulanti, Manon Yassawi, Reem |
| contents | Christol's theorem states that a power series with coefficients in a finite field is algebraic if and only if its coefficient sequence is automatic. A natural question is how the size of a polynomial describing such a sequence relates to the size of an automaton describing the same sequence. Bridy used tools from algebraic geometry to bound the size of the minimal automaton for a sequence, given its minimal polynomial. We produce a new proof of Bridy's bound by embedding algebraic sequences as diagonals of rational functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_10977 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An elementary proof of Bridy's theorem Rowland, Eric Stipulanti, Manon Yassawi, Reem Number Theory Formal Languages and Automata Theory Symbolic Computation 11B85, 13F25, 14H05 Christol's theorem states that a power series with coefficients in a finite field is algebraic if and only if its coefficient sequence is automatic. A natural question is how the size of a polynomial describing such a sequence relates to the size of an automaton describing the same sequence. Bridy used tools from algebraic geometry to bound the size of the minimal automaton for a sequence, given its minimal polynomial. We produce a new proof of Bridy's bound by embedding algebraic sequences as diagonals of rational functions. |
| title | An elementary proof of Bridy's theorem |
| topic | Number Theory Formal Languages and Automata Theory Symbolic Computation 11B85, 13F25, 14H05 |
| url | https://arxiv.org/abs/2308.10977 |