Fields of logic and computation II : essays dedicated to Yuri Gurevich on the occasion of his 75th birthday /: essays dedicated to Yuri Gurevich on the occasion of his 75th birthday. (2015)

• Record Type: Book
• Further Information: Note: Lev D. Beklemishev, Andreas Blass, Nachum Dershowitz, Bernd Finkbeiner, Wolfram Schulte (eds.).
• Editors: Beklemishev, Lev Dmitrievich, 1967-; Blass, Andreas, 1947-; Dershowitz, Nachum; Finkbeiner, Bernd; Schulte, Wolfram
• Other Names: Gurevich, Yuri honouree.; Yurifest (Symposium), 2nd
• Contents: Intro; Preface; Contents; K-trivial, K-low and MLR-low Sequences: A Tutorial; 1 Notation; 2 K-trivial Sets: Definition and Existence; 3 K-trivial and K-low Sequences; 4 K-trivial Sequences Cannot Compute 0'; 5 K-trivial Sequences Are K-low; 6 K-low and MLR-low Oracles; References; Horn Clause Solvers for Program Verification; 1 Introduction; 1.1 Program Logics and Horn Clauses; 1.2 Paper Outline; 2 Horn Clause Basics; 2.1 Existential Fixed-Point Logic and Horn Clauses; 2.2 Derivations and Interpretations; 2.3 Loose Semantics and Horn Clauses; 3 From Programs to Clauses; 3.1 State Machines 3.2 Procedural Languages3.3 Proof Rules; 4 Solving Horn Clauses; 4.1 Magic Sets; 4.2 Fold/Unfold; 4.3 A Program Transformation for Inlining Assertions; 5 Conclusions and Continuations; References; Existential Fixed-Point Logic as a Fragment of Second-Order Logic; 1 Introduction; 2 Preliminaries; 2.1 Existential Fixed-Point Logic; 2.2 Translation to Second-Order Logic; 3 Model-Checking; 4 Conjunctions; 5 Satisfiability and Trimming; 6 Trimming to Horn Form; 7 Summary; References; On the Unpredictability of Individual Quantum Measurement Outcomes; 1 Introduction; 2 Models of Prediction 3 A Model for Prediction of Individual Physical Events4 Computability Theoretic Notions of Unpredictability; 5 Quantum Unpredictability; 5.1 The Intuition of Quantum Indeterminism and Unpredictability; 5.2 A Formal Basis for Quantum Indeterminism; 5.3 Contextual Alternatives; 5.4 Unpredictability of Individual Quantum Measurements; 6 Incomputability, Unpredictability, and Quantum Randomness; 7 Summary; References; The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture; 1 Introduction; 2 Preliminaries; 3 The Ehrenfeucht-Fraïssé-method; 4 A Logical Reformulation of ¶=NP 5 On Random (3-Col, LFP)-Sequences6 The Planted Clique Conjecture; 7 The Planted Clique Conjecture and (3-Col, LFP)-sequences; 8 Some Remarks on the Logic Version of the Planted Clique Conjecture; 9 Further Results and Open Questions; References; Monadic Theory of a Linear Order Versus the Theory of its Subsets with the Lifted Min/Max Operations; 1 Introduction; 2 Preliminaries; 2.1 Linear Orders; 2.2 Logical Structures; 3 Lifted Structure; 3.1 The Semigroup ""426830A P(L), ""3222378 ""526930B; 3.2 A Characterization of the Operation ""3222378 3.3 The Partially Ordered Set ""426830A P(L), ""526930B3.4 Final Segments; 3.5 A Characterization of the Ordering; 4 Defining Single Elements; 4.1 Immediate Predecessors; 4.2 Singleton Sets; 4.3 Recovering the Linear Order; 4.4 Pairs; 5 Defining Membership; 5.1 Defining Final Segments; 5.2 Upwards Closure; 5.3 Membership When L has a Minimum Element 0; 5.4 Membership in the General Case; 6 Final Proofs; 6.1 Defining the Downarrow Operation with Uparrow; 6.2 Defining the Uparrow Operation with the Order; 6.3 Equivalent First-Order Structures; References
• Publisher Details: Cham : Springer
• Publication Date: 2015
• Extent: 1 online resource (x, 319 pages), illustrations
• Subjects: 005.101/5113; Computer science; Computer logic -- Congresses; Software engineering -- Congresses; Computer science -- Mathematics -- Congresses; Computer logic; Computer science -- Mathematics; Software engineering; Computer Science; Engineering & Applied Sciences; Computer Science; Programming Techniques; Computers -- Programming -- General; Computer programming / software development; Electronic books; Conference papers and proceedings; Electronic books
• Languages: English
• ISBNs: 9783319235349; 3319235346; 3319235338; 9783319235332
• Related ISBNs: 9783319235332
• Notes: Note: Online resource; title from PDF title page (SpringerLink, viewed September 11, 2015).
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.