Aspects Of Computation and Automata Theory With Applications

Contents
Foreword
Preface
Generators of the C.E. Degrees and Strongly Meet Inaccesssible Degrees
	1. Introduction
	2. Main Section
	3. Proof of Theorem 2.7
	4. Proof of Theorem 2.8
	5. Proof of Theorem 2.12
	6. Open Problems
	References
Cuts in the ML Degrees
	1. Introduction
	2. Proof of Proposition 1.4
		2.1. Verification
	References
Cantor–Bendixson Ranks for Almost Prime Models
	1. Introduction
	2. Preliminaries
		2.1. Prime models and decidable categoricity
		2.2. Types and Cantor–Bendixson ranks
		2.3. Related work
	3. Cantor–Bendixson Ranks and Almost Primeness
		3.1. Well-orders and Cantor–Bendixson ranks
		3.2. Finite Cantor–Bendixson ranks
	References
Isomorphism Types of Rogers Semilattices in the Analytical Hierarchy
	1. Introduction
	2. Preliminaries
		2.1. Numberings
		2.2. Related work
	3. Main Result
		3.1. Proof of Proposition 3.2
		3.2. Proof sketch for Proposition 3.3
		3.3. Proof of Proposition 3.4
	References
Immunity, Diagonalization and the Complexity of Mass Problems
	1. Introduction
		1.1. Classes defined via r.e. tools
		1.2. Classes defined via computable tools
	2. Locating the class EBI
		2.1. EBIs compute recursively bounded DNR functions
		2.2. A class between EBI and EI in terms of inclusion
		2.3. Descriptive complexity of the class of EBI sets
	3. Slowly-growing DNR functions
		3.1. Definitions and combinatorial lemmas
		3.2. Proof of Theorem 3.2
	4. Jump traceability implies a double lowness property
	5. DNR and SNPR functions
	6. Canonical immunity
	7. The SNR hierarchy
	8. Cardinal characteristics and prevalent numberings
	References
Computability and Categoricity of Weakly Homogeneous Boolean Algebras and p-Groups
	1. Introduction
	2. Abelian p-groups
		2.1. Torsion abelian groups
	3. Boolean Algebras
	Acknowledgements
	References
From Quasi-Dominions to Progress Measures
	1. Introduction
	2. Preliminaries
	3. Solving Parity Games via Progress Measures
		3.1. Measure-Function Spaces
		3.2. Progress-Measure Functions
	4. Solving Parity Games via Quasi-Dominion Measures
		4.1. Quasi-Dominion-Measure Functions
		4.2. Simple-Measure Functions
	5. A Concrete Algorithm
		5.1. A Concrete Measure Space
		5.2. The Solution Algorithm
	6. Experimental Evaluation
	7. Discussion
	Acknowledgments
	References
Effective Ultrapowers and Applications
	1. Introduction
	2. Computability-Theoretic Background
	3. Cohesive Products
	4. Isomorphism Types of Cohesive Powers of Q
	5. Automorphisms of Cohesive Powers of Q
	6. An Application of Cohesive Powers to Computable Algebra
	7. Additional Notes and Acknowledgements
	References
FPT-Inspired Approximations
	1. Introduction
	2. The general idea of using reduction rules for approximation
		2.1. Maximization problems
		2.2. Minimization problems
		2.3. A priori versus a posteriori analysis
	3. Reduction rules for approximating Minimum Total Dominating Set
		3.1. Problem description
		3.2. Designing reduction rules
		3.3. Useful combinatorial results
		3.4. Discussion of our findings
	4. Self-monitoring approximation algorithms for Minimum Vertex Cover
		4.1. A bird’s eye view on local ratio techniques
		4.2. Looking at bounded average-degree graphs
		4.3. Oblivious application of our algorithm
	5. Conclusions
	Acknowledgments
	References
Disjoint NP-Pairs and Propositional Proof Systems
	1. Introduction
	2. Separability and Reducibility
	3. Propositional Proof Systems
	4. Disjoint NP-Pairs that Are Complete or NP-Hard
	5. Optimal Propositional Proof Systems
	6. Canonical Disjoint NP-Pairs for Proof Systems
	7. Uniform Enumerations
	8. Relativization
		8.1. Existence of Optimal Proof Systems
		8.2. Do Complete Pairs Imply Optimal Proof Systems?
		8.3. P-Inseparable Pairs versus Optimal Proof Systems
		8.4. Separation of ESY-m, ESY-tt, and ESY-T
	9. Conclusion and Open Questions
	References
How to Verify Computations with a Rational Network
	1. Introduction
		1.1. The Verifier’s Dilemma
		1.2. Contribution of this chapter
		1.3. Incentives from cryptocurrencies
		1.4. Systems that outsource computation
		1.5. Our approach
	2. The Verification Game
	3. Frameworks of Consensus-Competition and Consensus-Contract
	4. A verification protocol with incentives
		4.1. Step 1: Presenting the puzzle
		4.2. Step 2: Committing a solution
		4.3. Selecting a subcommittee
		4.4. Playing the verification game
		4.5. Correctness and efficiency
	5. Practical considerations
		5.1. Outsourced computation
		5.2. Outsourced verification
	6. Conclusion
	References
Punctual Degrees and Lattice Embeddings
	1. Introduction
	2. Distributivity of lower cones
	3. No infimum
		3.1. Intuition
			3.1.1. The elementary diagonalisation strategy
			3.1.2. An informal description of the construction
		3.2. Formal proof
			3.2.1. The strategy for Ui
			3.2.2. The strategy for Ri
			3.2.3. The strategy for Se
			3.2.4. Construction
			3.2.5. Verification
	4. Embedding Int(η)
	5. Not a Boolean algebra. Proof of Theorem 1.5
		5.1. The definition of N(C, Pe)
		5.2. Pressing Pe
		5.3. The definition of L(C, Pe)
		5.4. Construction
		5.5. Verification
	Acknowledgments
	References
Maximal Automatic Complexity and Context-Free Languages
	1. Introduction
	2. Context-free languages
	3. Sensitivity of automatic complexity
		3.1. Defining the class SAC0
		3.2. Immunity to SAC0
	4. The class ⊕SAC0
	Acknowledgments
	References
Roots of Polynomials in Fields of Generalized Power Series
	1. Introduction
	2. Puiseux series
	3. Complexity in fields of Puiseux series
		3.1. Representing Puiseux series
		3.2. Complexity of basic operations
		3.3. Complexity of the root-taking process
	4. Hahn series
	5. Complexity in Hahn fields
		5.1. Mac Lane’s Theorem in admissible sets
		5.2. More precise results
		5.3. Complexity of basic operations
		5.4. Initial segments of roots
	References
A Scalable Verification Solution for Blockchains
	1. Securing computations with economics
		1.1. Outsourced computation
		1.2. Practical impact
		1.3. Smart contracts
	2. How TrueBit works
		2.1. System properties
		2.2. Assumptions
		2.3. Attacker model
	3. Dispute resolution layer
		3.1. Bottleneck: The Verifier’s Dilemma
		3.2. Solution: The verification game
		3.3. Detailed protocol
		3.4. Runtime and security analysis
	4. Incentive layer
		4.1. Jackpots
		4.2. Taxes
		4.3. Deposits
		4.4. Generating forced errors
		4.5. Solver and Verifier election
		4.6. Protocol overview
		4.7. Sanity check
	5. Defenses
		5.1. Pairwise Sybil attacks
		5.2. The trifecta
		5.3. Collusion pools
		5.4. On low-hanging fruit
		5.5. A cash equivalence problem
	6. Implementation
	7. Applications
		7.1. Practical decentralized pooled mining
		7.2. Dogecoin–Ethereum bridge
		7.3. Scalable transaction throughput
		7.4. Towards a big data system
	Acknowledgments
	8. Addendum
		8.1. Security patches
		8.2. The TrueBit Virtual Machine
		8.3. Additional applications
	References
Weak Muller Conditions Make Delay Games Hard
	1. Introduction
	2. Preliminaries
	3. Upper Bounds for Weak Muller Delay Games
	4. Lower Bounds for Deterministic Weak Muller Delay Games
	5. Lower Bounds for Non-Deterministic Weak Muller Delay Games
	6. Conclusion
	References
A Turing Machine like Model for Computation on Real Numbers
	1. Introduction
	2. Description of the Computation Model
		2.1. The Machine
		2.2. The Computation
	3. Computable Functions and Sets in the New Model
	Acknowledgments
	References