Fundamentals of Computation Theory

Fundamentals of Computation Theory: 21st International Symposium, FCT 2017, Bordeaux, France, September 11–13, 2017, Proceedings (Lecture Notes in Computer Science)

This book constitutes the refereed proceedings of the 21st International Symposium on Fundamentals of Computation Theory, FCT 2017, held in Bordeaux, France, in September 2017. The 29 revised full papers and 5 invited papers presented were carefully reviewed and selected from 99 submissions. The papers cover topics of all aspects of theoretical computer science, in particular algorithms, complexity, formal and logical methods.

Table of Contents

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