A Graphic Apology for Symmetry and Implicitness

Alessandra Carbone, Stephen Semmes (Autoren)

Buch | Hardcover

520 Seiten

2000
Oxford University Press (Verlag)
978-0-19-850729-1 (ISBN)

Artikel merken

Succinct representation and fast access to large amounts of data are challenges of our time. This unique book suggests general approaches of 'complexity of descriptions'. It deals with a variety of concrete topics and bridges between them, while opening new perspectives and providing promising avenues for the 'complexity puzzle'.

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