5 papers
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…
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…
The Railroad Crossing Problem: An Experiment with Instantaneous Actions and Immediate Reactions
Yuri Gurevich, James K. Huggins
We give an evolving algebra solution for the well-known railroad crossing problem and use the occasion to experiment with agents that perform instantaneous actions in continuous ti…
Evolving Algebras and Partial Evaluation
Yuri Gurevich, James K. Huggins
We describe an automated partial evaluator for evolving algebras implemented at the University of Michigan.
Equivalence is in the Eye of the Beholder
Yuri Gurevich, James K. Huggins
In a recent provocative paper, Lamport points out "the insubstantiality of processes" by proving the equivalence of two different decompositions of the same intuitive algorithm by…