The pillars of computation theory. State, encoding, nondeterminism

DOI10.1007/978-0-387-09639-1zbMath1203.68050OpenAlexW2490930245MaRDI QIDQ1039511

Arnold L. Rosenberg

Publication date: 30 November 2009

Published in: Universitext (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-0-387-09639-1

zbMATH Keywords

binary relationfinite automatatime complexitycomplexity theorycomputation theoryspace complexityMyhill-Nerode theoremnondeterministic Turing machineonline automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

A class of recursive permutations which is primitive recursive complete

This page was built for publication: The pillars of computation theory. State, encoding, nondeterminism