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

This Festschrift is published in honor of Yuri Gurevich’s 80th birthday. An associated conference, YuriFest 2020, was planned for May 18–20 in Fontainebleau, France, in combination with the 39th Journées sur les Arithmétiques Faibles also celebrating Yuri’s 80th birthday. Because of the coronavirus situation, the conference had to be postponed, but this Festschrift is being published as originally planned. It addresses a very wide variety of topics, but by no means all of the fields of logic and computation in which Yuri has made important progress. Front Matter ....Pages i-x Front Matter ....Pages 1-1 To Yuri at 80 and More than 40 Years of Friendship (Johann A. Makowsky)....Pages 3-6 Front Matter ....Pages 7-7 State of the Art in Logics for Verification of Resource-Bounded Multi-Agent Systems (Natasha Alechina, Brian Logan)....Pages 9-29 Why Predicative Sets? (Arnon Avron)....Pages 30-45 Functional Thesauri, Classifying Topoi, Unification, and Flatness (Andreas Blass)....Pages 46-56 Parameterized Parallel Computing and First-Order Logic (Yijia Chen, Jörg Flum)....Pages 57-78 Betweenness in Order-Theoretic Trees (Bruno Courcelle)....Pages 79-94 Relativization of Gurevich’s Conjectures (Anatole Dahan, Anuj Dawar)....Pages 95-104 Seventy Years of Computer Science (Martin Davis)....Pages 105-117 Convergence and Nonconvergence Laws for Random Expansions of Product Structures (Anuj Dawar, Erich Grädel, Matthias Hoelzel)....Pages 118-132 Medieval Arabic Notions of Algorithm: Some Further Raw Evidence (Wilfrid Hodges)....Pages 133-146 On the Generalized Membership Problem in Relatively Hyperbolic Groups (Olga Kharlampovich, Pascal Weil)....Pages 147-155 Identities of the Kauffman Monoid \(\mathcal {K}_4\) and of the Jones Monoid \(\mathcal {J}_4\) (Nikita V. Kitov, Mikhail V. Volkov)....Pages 156-178 Relativistic Effects Can Be Used to Achieve a Universal Square-Root (Or Even Faster) Computation Speedup (Olga Kosheleva, Vladik Kreinovich)....Pages 179-189 Towards Verifying Logic Programs in the Input Language of clingo (Vladimir Lifschitz, Patrick Lühne, Torsten Schaub)....Pages 190-209 Computing on Lattice-Ordered Abelian Groups (Daniele Mundici)....Pages 210-225 The Expressive Power of Temporal and First-Order Metric Logics (Alexander Rabinovich)....Pages 226-246 Two First-Order Theories of Ordinals (Peter H. Schmitt)....Pages 247-257 Randomness Tests: Theory and Practice (Alexander Shen)....Pages 258-290 On Entropic Convergence of Algorithms (Anatol Slissenko)....Pages 291-304 The Power of Spreadsheet Computations (Jerzy Tyszkiewicz)....Pages 305-322 Non-Algorithmic Theory of Randomness (Vladimir Vovk)....Pages 323-340 Back Matter ....Pages 341-341