Deciding ω-Regular Properties on Linear Recurrence Sequences
summary
A procedure inputs a prefix‑independent ω‑regular condition and a linear recurrence sequence and decides whether the sequence’s sign word satisfies it, but only when the recurrence is simple (diagonalizable). The core lemma shows the sign description is almost periodic for such sequences; proof uses algebraic number theory, the Subspace Theorem and bounds on sums of S‑units, and a non‑effective threshold n0 that forces the prefix‑independence restriction. A non‑diagonalizable counterexample breaks almost periodicity.
AI-written summary · about