Fields of Logic and Computation II: Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday (Lecture Notes in Computer Science Book 9300)

This Festschrift is published in honor of Yuri Gurevich's 75th birthday. Yuri Gurevich has made fundamental contributions on the broad spectrum of logic and computer science, including decision procedures, the monadic theory of order, abstract state machines, formal methods, foundations of computer science, security, and much more. Many of these areas are reflected in the 20 articles in this Festschrift and in the presentations at the "Yurifest" symposium, which was held in Berlin, Germany, on September 11 and 12, 2015. The Yurifest symposium was co-located with the 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). 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 Fields of Logic and Computation II This Festschrift has been published in honor of Yuri Gurevich, on the occasion of his 75th birthday. Yuri Gurevich has made a number of fundamental contributions℗l to the broad spectrum of logic and computer science, including decision procedures, the monadic theory of order, abstract state machines, formal methods, foundations of computer science, security, and much more. Many of these areas are reflected in the 20 articles in this Festschrift and in the presentations at the ĺlYurifestĺl symposium, which was held in Berlin, Germany, on September 11 and 12, 2015. The Yurifest symposium was co-located with the℗l24th EACSL Annual Conference on Computer Science Logic (CSL 2015) Fields of Logic and Computation II This Festschrift has been published in honor of Yuri Gurevich, on the occasion of his 75th birthday. Yuri Gurevich has made a number of fundamental contributions to the broad spectrum of logic and computer science, including decision procedures, the monadic theory of order, abstract state machines, formal methods, foundations of computer science, security, and much more. Many of these areas are reflected in the 20 articles in this Festschrift and in the presentations at the "Yurifest" symposium, which was held in Berlin, Germany, on September 11 and 12, 2015. The Yurifest symposium was co-located with the 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)