2009/11/12 by Jason P. Bell, Jason Bell, Bell, Jason +4
Chemistry · Computer Science · Mathematics · #03C13 #05A15 #Chemistry and Stereochemistry Studies #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Logic (math.LO) #Topological and Geometric Data Analysis #math.CO #math.LO #msc:03C13 #msc:05A15
paper · pdf · doi:10.48550/arxiv.0911.2494
46 pages
arxiv created 2009/11/12 · openalex publication_date 2009/11/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a previous work we introduced an elementary method to analyze the periodicity of a generating function defined by a single equation y=G(x,y). This was based on deriving a single set-equation Y = Gammma(Y) defining the spectrum of the generating function. This paper focuses on extending the analysis of periodicity to generating functions defined by a system of equations y = G(x,y). The final section looks at periodicity results for the spectra of monadic second-order classes whose spectrum is determined by an equational specification - an observation of Compton shows that monadic-second order classes of trees have this property. This section concludes with a substantial simplification of the proofs in the 2003 foundational paper on spectra by Gurevich and Shelah, namely new proofs are given of: (1) every monadic second-order class of m-colored functional digraphs is eventually periodic, and (2) the monadic second-order theory of finite trees is decidable.