Complexité et décidabilité / Patrick Dehornoy

Auteur: Dehornoy, Patrick (1952-) - AuteurType de document: MonographieCollection: Mathématiques et applications ; 12Langue: françaisPays: FranceÉditeur: Paris : Springer, 1993Description: 1 vol. (200 p.) ; 24 cm ISBN: 2287004165 ; br. Résumé: This book is the supporting text of the course taught by the author at the University of Caen. It includes main results in complexity theory concerning first-order logic. The author emphasizes on the main negative results concerning the complexity of Boolean calculus, first-order logic and of arithmetic. The theory is presented in the standard model of Turing machines. The model is largely studied in the first six chapters of the book. Thus, the reader may not be familiar with complexity and even logic theories. We note the elegant manner the author succeeds in giving a rigorous and at the same time easy to understand presentation of some difficult results. Here are the chapters of the book: 1. Algorithmes et machines de Turing, 2. Simulation d’algorithmes, 3. Changement de réprésentation, 4. Fonctions récursives, 5. Machines universelles, 6. Machines non déterministes, 7. Complexité du calcul booléen, 8. Complexité des logiques du premier ordre, 9. Complexité de l’arithmétique, 10. Complexité de l’addition des entiers. (Zentralblatt).Bibliographie: Bibliogr. p. 195-197. Index. Sujets MSC: 03D15 Mathematical logic and foundations -- Computability and recursion theory -- Complexity of computation
03D10 Mathematical logic and foundations -- Computability and recursion theory -- Turing machines and related notions
03B25 Mathematical logic and foundations -- General logic -- Decidability of theories and sets of sentences
68Q05 Computer science -- Theory of computing -- Models of computation (Turing machines, etc.)
68Q15 Computer science -- Theory of computing -- Complexity classes (hierarchies, relations among complexity classes, etc.)
En-ligne: Zentralblatt | MathSciNet
Location Call Number Status Date Due
Couloir 10948-01 / Séries SMA (Browse Shelf) Available
Couloir 10948-02 / Séries SMA (Browse Shelf) Available

Bibliogr. p. 195-197. Index

This book is the supporting text of the course taught by the author at the University of Caen. It includes main results in complexity theory concerning first-order logic. The author emphasizes on the main negative results concerning the complexity of Boolean calculus, first-order logic and of arithmetic. The theory is presented in the standard model of Turing machines. The model is largely studied in the first six chapters of the book. Thus, the reader may not be familiar with complexity and even logic theories. We note the elegant manner the author succeeds in giving a rigorous and at the same time easy to understand presentation of some difficult results.

Here are the chapters of the book: 1. Algorithmes et machines de Turing, 2. Simulation d’algorithmes, 3. Changement de réprésentation, 4. Fonctions récursives, 5. Machines universelles, 6. Machines non déterministes, 7. Complexité du calcul booléen, 8. Complexité des logiques du premier ordre, 9. Complexité de l’arithmétique, 10. Complexité de l’addition des entiers. (Zentralblatt)

There are no comments for this item.

Log in to your account to post a comment.
Languages: English | Français | |