Spectra and Systems of Equations

Details Spectra and Systems of Equations Spectra and Systems of Equations

2009-11-12

arxiv.org/abs/0911.2494v1

Mathematics

Logic

46 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Spectra and Systems of Equations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spectra and Systems of Equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spectra and Systems of Equations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-148851