Sinopsis
John C. Martin realizó sus estudios en la Rice University, donde obtuvo en 1966 la licenciatura en matemáticas y en 1971 el doctorado. Impartió cátedra durante dos años en la University of Hawai en Honolulu, antes de integrarse a la North Dakota State University, donde es profesor asociado de ciencias de la computación.Es un tratado de la teoría de la computación con énfasis en los lenguajes formales, autómatas y modelos abstractos de computación y de computabilidad; también incluye una introducción a la complejidad computacional y a los problemas NP completos.
Indice
1. Objetos matemáticos básicos.
2. Introducción matemática y definiciones recursivas.
3. Expresiones regulares y autómatas finitos.
4. No determinismo y el teorema de Kleene.
5. Lenguajes regulares y no regulares.
6. Gramáticas de contexto libre.
7. Autómatas con pila.
8. Lenguajes de contexto libre y lenguajes que no son de contexto libre.
9. Máquinas de Turing.
10. Lenguajes enumerables recursivamente.
11. Problemas insolubles.
12. Funciones computables.
13. Medición y clasificación de la complejidad.
14. Problemas tratables e intratables.
Información bibliográfica
ISBN: 9789701045947
AUTOR: MARTIN
EDITORIAL: MCGRAW-HILL
AÑO: 2004
ÁREA: COMPUTACION