Showing math.LOShow all
2 papers · 1 filter
math.LO2004
Spectra of Monadic Second-Order Formulas with One Unary Function
Yuri Gurevich, Saharon Shelah
We establish the eventual periodicity of the spectrum of any monadic second-order formula where: (i) all relation symbols, except equality, are unary, and (ii) there is only one fu…
math.LO2001
On Polynomial Time Computation Over Unordered Structures
Andreas Blass, Yuri Gurevich, Saharon Shelah
This paper is motivated by the question whether there exists a logic capturing polynomial time computation over unordered structures. We consider several algorithmic problems near…