|
|
|
|
|
|
|
|
|
1. |
Record Nr. |
UNISA996466457103316 |
|
|
Titolo |
Fields of Logic and Computation II [[electronic resource] ] : Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday / / edited by Lev D. Beklemishev, Andreas Blass, Nachum Dershowitz, Bernd Finkbeiner, Wolfram Schulte |
|
|
|
|
|
|
|
Pubbl/distr/stampa |
|
|
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 |
|
|
|
|
|
|
|
|
|
ISBN |
|
|
|
|
|
|
Edizione |
[1st ed. 2015.] |
|
|
|
|
|
Descrizione fisica |
|
1 online resource (X, 319 p. 15 illus.) |
|
|
|
|
|
|
Collana |
|
Programming and Software Engineering ; ; 9300 |
|
|
|
|
|
|
Disciplina |
|
|
|
|
|
|
Soggetti |
|
Computer programming |
Programming Techniques |
|
|
|
|
|
|
|
|
Lingua di pubblicazione |
|
|
|
|
|
|
Formato |
Materiale a stampa |
|
|
|
|
|
Livello bibliografico |
Monografia |
|
|
|
|
|
Note generali |
|
Bibliographic Level Mode of Issuance: Monograph |
|
|
|
|
|
|
Nota di contenuto |
|
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 Languages -- 3.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 Events -- 4 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)-Sequences -- 6 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), "526930B -- 3.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 -- Regularity Equals Monadic Second-Order Definability for Quasi-trees -- 1 Introduction -- 2 Definitions, Notation and Basic Facts -- 2.1 Finite and Infinite Terms -- 2.2 Arrangements -- 2.3 Trees and Rooted Trees -- 2.4 Join-Trees -- 2.5 The Rank-Width of a Countable Graph -- 3 The Algebra of Binary Join-Trees -- 4 Quasi-trees -- References -- Capturing MSO with One Quantifier -- 1 Introduction -- 2 Preliminaries -- 3 Satisfiability Quantifier -- 4 Capturing MSO -- 5 Unranked Trees -- 6 Conclusion -- References -- Logics for Weighted Timed Pushdown Automata -- 1 Introduction -- 2 Weighted Timed Pushdown Automata -- 3 Weighted Timed Matching Logic. |
4 Visibly Pushdown Languages -- 5 Decomposition of Weighted Timed Pushdown Automata -- 6 Definability Equals Recognizability -- 7 Weighted Timed Pushdown Automata with Global Clocks -- 8 Conclusion -- References -- Inherent Vacuity in Lattice Automata -- 1 Introduction -- 2 Preliminaries -- 2.1 Lattices -- 2.2 Lattice Automata -- 3 Vacuity in Lattice Automata -- 4 Useful Observations on Tolerance and Flexibility -- 4.1 Full-Order LDFW -- 4.2 Full-Order LNFW -- 4.3 Partial-Order LDFW -- 4.4 Partial-Order LNFW -- 5 Complexity of the Decision Problems -- 6 Inherent Vacuity with Analogy to Temporal Logic -- References -- Is Polynomial Time Choiceless? -- 1 Introduction -- 2 Choiceless Polynomial Time -- 2.1 BGS-Logic -- 2.2 Definition of Choiceless Polynomial Time -- 2.3 Defining Properties of Small Substructures -- 2.4 Choiceless Polynomial Time Without Counting -- 3 Fixed-Point Logic with Counting -- 4 Structures of Bounded Colour Class Size -- 5 Symmetric Circuits -- 6 Interpretation Logic -- 7 Challenges for Future Research -- 7.1 A Characterization Without Explicit Polynomial Bounds -- 7.2 Polynomial-Time Properties of Small Definable Subgraphs -- 7.3 Isomorphism of CFI-Graphs and Graphs of Bounded Colour Class Size -- 7.4 Constraint Satisfaction Problems -- 7.5 A Notion of Symmetric Circuits for CPT -- 7.6 Choiceless Polynomial Time versus Rank Logic -- References -- Arithmetical Congruence Preservation: From Finite to Infinite -- 1 |
|
|
|
|
|
|
|
|
|
Introduction -- 2 Switching Between Finite and Infinite -- 2.1 Lifting Functions Z/nZZ/mZ to NN and ZZ -- 2.2 Representation of Congruence Preserving Functions Z/nZZ/mZ -- 2.3 Lifting Functions Z/nZZ/mZ to Z/rZZ/sZ -- 3 Congruence Preservation on p-adic/profinite Integers -- 3.1 Congruence Preserving Functions Are Continuous -- 3.2 Congruence Preserving Functions and Inverse Limits. |
3.3 Extension of Congruence Preserving Functions NN -- 3.4 Representation of Congruence Preserving Functions ZpZp -- 4 Conclusion -- References -- An Extension of the Ehrenfeucht-Fraïssé Game for First Order Logics Augmented with Lindström Quantifiers -- 1 Introduction -- 2 The Game -- 2.1 Description of the First Game -- 2.2 A Game Where Definability is Not Forced -- 2.3 A Game with Fixed Game-Board and Fixed Roles -- 3 Summary -- References -- Logics of Finite Hankel Rank -- 1 Introduction -- 1.1 Yuri's Quest for Logics for Computer Science -- 1.2 Preservation Theorems -- 1.3 Reduction Theorems -- 1.4 Purpose of This Paper -- 2 Background -- 2.1 Logics with Quantifier Rank -- 2.2 Sum-Like and Product-Like Operations on -structures -- 2.3 Abstract Lindström Logics -- 3 Hankel Matrices of -properties -- 3.1 Hankel Matrices -- 3.2 -Properties of Finite -rank -- 3.3 Proof of Theorem 5 -- 3.4 Properties of Finite S-rank and Finite P-rank -- 4 Hankel Matrices and the Feferman-Vaught Theorem -- 4.1 The FV-property -- 4.2 The FV-property and Finite Rank -- 5 The S-Closure of a Nice Logic -- 6 Conclusions and Open Problems -- References -- The Strategy of Campaigning -- 1 Introduction -- 2 A General Theorem -- 3 Ambiguity and Pessimism -- 4 The Logical Formalism of Dean and Parikh -- 5 Extension of the Framework -- 5.1 Candidate Beliefs -- 5.2 Stay-At-Home Voters -- 6 Conclusions and Future Work -- References -- On Almost Future Temporal Logics -- 1 Introduction -- 2 Preliminaries -- 2.1 First-Order Monadic Logic of Order -- 2.2 Propositional Temporal Logics -- 2.3 Kamp's and Stavi's Theorems -- 3 Future and Almost Future Formulas -- 4 No Finite Base for Almost Future Formulas -- 4.1 Proof of Lemma 4.3 -- 4.2 Proof of Lemma 4.4 -- 4.3 A Generalization -- References -- Minsky Machines and Algorithmic Problems -- 1 Introduction. |
2 Turing Machines and Minsky Machines -- 2.1 Turing Machines -- 2.2 Minsky Machines -- 3 The Three Main Semigroups Simulating Minsky Machines -- 4 Varieties of Semigroups and the Word Problem -- 5 Gurevich's Theorem. The Uniform Word Problem for Finite Semigroups -- 6 The Uniform Word Problem for Finite Groups -- 6.1 Slobodskoi's Theorem -- 6.2 Some Applications of Slobodskoi's Theorem -- 7 Other Algorithmic Applications of Minsky Machines -- 7.1 Collatz Type Problems -- 7.2 Amalgams of Finite Semigroups -- 7.3 Complicated Residually Finite Semigroups -- References -- On Failure of 0-1 Laws -- References -- Composition Over the Natural Number Ordering with an Extra Binary Relation -- 1 Introduction -- 2 (N, <, P) with Monadic P -- 3 (N, <, R) with Binary R of Finite Valency -- 4 Applications -- 5 Conclusion -- References -- The Fundamental Nature of the Log Loss Function -- 1 Introduction -- 2 Loss Functions -- 3 Repetitive Predictions -- 4 A Simple Statement of Fundamentality -- 5 A Criterion of Fundamentality -- 6 Frequently Asked Questions -- 7 Conclusion -- References -- Erratum to: The Fundamental Natureof the Log Loss Function -- Author Index. |
|
|
|
|
|
|
Sommario/riassunto |
|
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). |
|
|
|
|
|
| |