Fields of Logic and Computation II

Name: Fields of Logic and Computation II | Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday

Lev D. Beklemishev Andreas Blass Nachum Dershowitz Bernd Finkbeiner Wolfram Schulte(Editor)

Springer (Publisher)

Published on 5. September 2015

X, 319 pages

E-Book

PDF with digital watermarking

System requirements

978-3-319-23534-9 (ISBN)

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

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

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Fields of Logic and Computation II

Description

More details

Other editions

Additional editions

Content

System requirements