Fundamentals of Computation Theory

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Automata and Program Analysis
3. Altmetric Badge
   Chapter 2 What One Has to Know When Attacking $$\textsf {P}$$ vs. $$\textsf {NP}$$ (Extended Abstract)
4. Altmetric Badge
   Chapter 3 A Tour of Recent Results on Word Transducers
5. Altmetric Badge
   Chapter 4 Some Results of Zoltán Ésik on Regular Languages
6. Altmetric Badge
   Chapter 5 Contextuality in Multipartite Pseudo-Telepathy Graph Games
7. Altmetric Badge
   Chapter 6 Generalized Satisfiability Problems via Operator Assignments
8. Altmetric Badge
   Chapter 7 New Results on Routing via Matchings on Graphs
9. Altmetric Badge
   Chapter 8 Energy-Efficient Fast Delivery by Mobile Agents
10. Altmetric Badge
    Chapter 9 Parameterized Aspects of Triangle Enumeration
11. Altmetric Badge
    Chapter 10 Testing Polynomial Equivalence by Scaling Matrices
12. Altmetric Badge
    Chapter 11 Strong Duality in Horn Minimization
13. Altmetric Badge
    Chapter 12 Token Jumping in Minor-Closed Classes
14. Altmetric Badge
    Chapter 13 Expressive Power of Evolving Neural Networks Working on Infinite Input Streams
15. Altmetric Badge
    Chapter 14 Minimal Absent Words in a Sliding Window and Applications to On-Line Pattern Matching
16. Altmetric Badge
    Chapter 15 Subquadratic Non-adaptive Threshold Group Testing
17. Altmetric Badge
    Chapter 16 The Snow Team Problem
18. Altmetric Badge
    Chapter 17 FO Model Checking on Map Graphs
19. Altmetric Badge
    Chapter 18 Multiple Context-Free Tree Grammars and Multi-component Tree Adjoining Grammars
20. Altmetric Badge
    Chapter 19 On $$\varSigma \wedge \varSigma \wedge \varSigma $$ Circuits: The Role of Middle $$\varSigma $$ Fan-In, Homogeneity and Bottom Degree
21. Altmetric Badge
    Chapter 20 Decidable Weighted Expressions with Presburger Combinators
22. Altmetric Badge
    Chapter 21 The Complexity of Routing with Few Collisions
23. Altmetric Badge
    Chapter 22 Parikh Image of Pushdown Automata
24. Altmetric Badge
    Chapter 23 Tropical Combinatorial Nullstellensatz and Fewnomials Testing
25. Altmetric Badge
    Chapter 24 On Weak-Space Complexity over Complex Numbers
26. Altmetric Badge
    Chapter 25 Deterministic Oblivious Local Broadcast in the SINR Model
27. Altmetric Badge
    Chapter 26 Undecidability of the Lambek Calculus with Subexponential and Bracket Modalities
28. Altmetric Badge
    Chapter 27 Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words
29. Altmetric Badge
    Chapter 28 Listing All Fixed-Length Simple Cycles in Sparse Graphs in Optimal Time
30. Altmetric Badge
    Chapter 29 Reliable Communication via Semilattice Properties of Partial Knowledge
31. Altmetric Badge
    Chapter 30 Polynomial-Time Algorithms for the Subset Feedback Vertex Set Problem on Interval Graphs and Permutation Graphs
32. Altmetric Badge
    Chapter 31 Determinism and Computational Power of Real Measurement-Based Quantum Computation
33. Altmetric Badge
    Chapter 32 Busy Beaver Scores and Alphabet Size
34. Altmetric Badge
    Chapter 33 Automatic Kolmogorov Complexity and Normality Revisited