P-Recursive Integer Sequences and Automata Theory

摘要: Author(s): Garrabrant, Scott Michael | Advisor(s): Pak, Igor Abstract: An integer sequence {a n } is called polynomially recursive, or P-recursive, if it satisfies a nontrivial linear recurrence relation of the formq_0(n)a_n + q_1(n)a_{n−1} . q_k(n)a_{n−k} = 0 ,for some q_i(x) ∈ Z[x], ≤ i k. The study P-recursive sequences plays major role in modern Enumerative and Asymptotic Combinatorics. have D-finite (also holonomic) generating functions.This dissertation on application automata theory to analysis sequences, broken into three self-contained chapters. Chapters 1 2 contain negative results, simulating Turing machines within combinatorial structures show these are not counted by sequence. In Chapter 1, we answer question Maxim Kontsevich showing [1]u_n always when u Z[GL(k, Z)]. 2, disprove celebrated Noonan-Zeilberger conjecture that pattern avoidance P-recursive. These two chapters give first results P-recursiveness using theory. Historically, this form been mostly proven asymptotics.Chapter 3 gives full class counting irrational tilings constant height strip. This subset prove equivalence definitions class: functions tilings, binomial multisums, diagonals N-rational functions. analysis, count paths through labelled graph way equivalent strings accepted given deterministic finite automaton where each letter appears times.