Yuri Gurevich has played a major role in the discovery and development of - plications of mathematical logic to theoretical and practical computer science. His interests have spanned a broad spectrum of subjects, including decision p- cedures, the monadic theory of order, abstract state machines, formal methods, foundations of computer science, security, and much more. In May 2010, Yuri celebrated his 70th birthday. To mark that occasion, on August 22, 2010,a symposium was held in Brno, the Czech Republic, as a sat- lite event of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010) and of the 19th EACSL Annual Conference on Computer Science Logic (CSL 2010). The meeting received generous support from Microsoft Research. In preparation for this 70th birthday event, we asked Yuri’s colleagues (whether or not they were able to attend the symposium) to contribute to a volume in his honor. This book is the result of that e?ort. The collection of articles herein begins with an academic biography, an annotated list of Yuri’s publications and reports, and a personaltribute by Jan Van den Bussche. These are followed by 28 technical contributions. These articles – though they cover a broad range of topics – represent only a fraction of Yuri’s multiple areas of interest. Each contribution was reviewed by one or two readers. In this regard, the editors wish to thank several anonymous individuals for their assistance.
Author(s): Andreas Blass, Nachum Dershowitz, Wolfgang Reisig (auth.), Andreas Blass, Nachum Dershowitz, Wolfgang Reisig (eds.)
Series: Lecture Notes in Computer Science 6300 : Programming and Software Engineering
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 627
Tags: Logics and Meanings of Programs; Software Engineering; Mathematical Logic and Formal Languages; Algorithm Analysis and Problem Complexity; Computer Communication Networks; Programming Languages, Compilers, Interpreters
Front Matter....Pages -
Yuri, Logic, and Computer Science....Pages 1-48
Database Theory, Yuri, and Me....Pages 49-60
Tracking Evidence....Pages 61-74
Strict Canonical Constructive Systems....Pages 75-94
Decidable Expansions of Labelled Linear Orderings....Pages 95-107
Existential Fixed-Point Logic, Universal Quantifiers, and Topoi....Pages 108-134
Three Paths to Effectiveness....Pages 135-146
The Quest for a Tight Translation of Büchi to co-Büchi Automata....Pages 147-164
Normalization of Some Extended Abstract State Machines....Pages 165-180
Finding Reductions Automatically....Pages 181-200
On Complete Problems, Relativizations and Logics for Complexity Classes....Pages 201-207
Effective Closed Subshifts in 1D Can Be Implemented in 2D....Pages 208-226
The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey....Pages 227-250
A Logic for PTIME and a Parameterized Halting Problem....Pages 251-276
Inferring Loop Invariants Using Postconditions....Pages 277-300
ASMs and Operational Algorithmic Completeness of Lambda Calculus....Pages 301-327
Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs....Pages 328-353
Ibn Sīnā on Analysis: 1. Proof Search. Or: Abstract State Machines as a Tool for History of Logic....Pages 354-404
Abstract State Machines and the Inquiry Process....Pages 405-413
The Algebra of Adjacency Patterns: Rees Matrix Semigroups with Reversion....Pages 414-443
Definability of Combinatorial Functions and Their Linear Recurrence Relations....Pages 444-462
Halting and Equivalence of Program Schemes in Models of Arbitrary Theories....Pages 463-469
Metrization Theorem for Space-Times: From Urysohn’s Problem towards Physically Useful Constructive Mathematics....Pages 470-487
Thirteen Definitions of a Stable Model....Pages 488-503
DKAL and Z3: A Logic Embedding Experiment....Pages 504-528
Decidability of the Class E by Maslov’s Inverse Method....Pages 529-537
Logics for Two Fragments beyond the Syllogistic Boundary....Pages 538-564
Choiceless Computation and Symmetry....Pages 565-580
Hereditary Zero-One Laws for Graphs....Pages 581-614
On Monadic Theories of Monadic Predicates....Pages 615-626
Back Matter....Pages -
