Fields of Logic and Computation II: Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday

Front Matter....Pages I-X
  \(\textit{K}\) -trivial,  \(\textit{K}\) -low and  \({{\mathrm{\textit{MLR}}}}\) -low Sequences: A Tutorial....Pages 1-23
Horn Clause Solvers for Program Verification....Pages 24-51
Existential Fixed-Point Logic as a Fragment of Second-Order Logic....Pages 52-68
On the Unpredictability of Individual Quantum Measurement Outcomes....Pages 69-86
The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture....Pages 87-108
Monadic Theory of a Linear Order Versus the Theory of its Subsets with the Lifted Min/Max Operations....Pages 109-128
Regularity Equals Monadic Second-Order Definability for Quasi-trees....Pages 129-141
Capturing MSO with One Quantifier....Pages 142-152
Logics for Weighted Timed Pushdown Automata....Pages 153-173
Inherent Vacuity in Lattice Automata....Pages 174-192
Is Polynomial Time Choiceless?....Pages 193-209
Arithmetical Congruence Preservation: From Finite to Infinite....Pages 210-225
An Extension of the Ehrenfeucht-Fraïssé Game for First Order Logics Augmented with Lindström Quantifiers....Pages 226-236
Logics of Finite Hankel Rank....Pages 237-252
The Strategy of Campaigning....Pages 253-260
On Almost Future Temporal Logics....Pages 261-272
Minsky Machines and Algorithmic Problems....Pages 273-292
On Failure of 0-1 Laws....Pages 293-296
Composition Over the Natural Number Ordering with an Extra Binary Relation....Pages 297-306
The Fundamental Nature of the Log Loss Function....Pages 307-318
Back Matter....Pages 319-319