A Graphic Apology for Symmetry and Implicitness by Alessandra CarboneA Graphic Apology for Symmetry and Implicitness by Alessandra Carbone

A Graphic Apology for Symmetry and Implicitness

byAlessandra Carbone, Stephen Semmes

Hardcover | September 1, 2000

Pricing and Purchase Info


Earn 2,175 plum® points

Prices and offers may vary in store


In stock online

Ships free on orders over $25

Not available in stores


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 - butobjects 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
Title:A Graphic Apology for Symmetry and ImplicitnessFormat:HardcoverPublished:September 1, 2000Publisher:Oxford University PressLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:0198507291

ISBN - 13:9780198507291


Table of Contents

1. Introduction2. Morphisms in logic and complexity3. Exponential processes and formal proofs4. Graphs and their visibilities5. Asymptotic growth of infinite visibilities6. Geometric aspects of cut elimination7. Feasibility graphs8. Bounds for finite visibilities9. Some related computational questions10. Mappings and graphs11. Mappings and comparisons12. Adjacency matrices and counting13. Duality and NP-completeness14. Finite automata and regular languages15. Constructions with graphs16. Stronger forms of recursion17. Groups and graphs18. Extended notions of automata19. Geometry of scales in metric spaces20. The Corona decomposition revisitedAppendix A: Formal proofs: A brief reviewReferencesIndex