A Graphic Apology for Symmetry and Implicitness
Oxford University Press (Verlag)
978-0-19-850729-1 (ISBN)
The present book brings into focus the contrast between explicit and implicit algorithmic descriptions of objects. These themes are considered in a variety of settings, sometimes crossing traditional boundaries. Special emphasis is given to moderate complexity - exponential or polynomial - but objects with multi-exponential complexity also fit in. Among the items under consideration are graphs, formal proofs, languages, automata, groups, circuits, some connections with geometry of metric spaces, and complexity classes (P, NP, co-NP).
A. Carbone, Associate Professor of Computer Science, University of Paris XII, France S. Semmes, Professor of Mathematics, Rice University, Houston, USA
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
| Erscheint lt. Verlag | 13.7.2000 |
|---|---|
| Reihe/Serie | Oxford Mathematical Monographs |
| Zusatzinfo | numerous line figures |
| Verlagsort | Oxford |
| Sprache | englisch |
| Maße | 162 x 242 mm |
| Gewicht | 864 g |
| Themenwelt | Geisteswissenschaften ► Philosophie ► Logik |
| Mathematik / Informatik ► Informatik ► Theorie / Studium | |
| Mathematik / Informatik ► Mathematik ► Graphentheorie | |
| Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre | |
| ISBN-10 | 0-19-850729-1 / 0198507291 |
| ISBN-13 | 978-0-19-850729-1 / 9780198507291 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
