Readership: Graduate mathematics students and researchers working on logic, combinatorics, group theory, and geometry. Graduate students and researchers in computer science working on logic, automated deduction, complexity theory, and formal language theory.
Alessandra Carbone, Department of Mathematics and Computer Science, University of Paris XII, and Stephen Semmes, Department of Mathematics, Rice University, Houston
"... outstanding ... The reviewer highly recommends this novel and interesting monograph." - Zentralblatt Math
"Interesting and this is certainly one of the first treatments of these problems." - EMS
1: Introduction 2: Morphisms in logic and complexity 3: Exponential processes and formal proofs 4: Graphs and their visibilities 5: Asymptotic growth of infinite visibilities 6: Geometric aspects of cut elimination 7: Feasibility graphs 8: Bounds for finite visibilities 9: Some related computational questions 10: Mappings and graphs 11: Mappings and comparisons 12: Adjacency matrices and counting 13: Duality and NP-completeness 14: Finite automata and regular languages 15: Constructions with graphs 16: Stronger forms of recursion 17: Groups and graphs 18: Extended notions of automata 19: Geometry of scales in metric spaces 20: The Corona decomposition revisited Appendix A: Formal proofs: A brief review References Index
