The pillars of computation theory: state, encoding, nondeterminism/
Arnold L. Rosenberg
- New York: Springer, 2010.
- xvii, 324 p. : ill. ; 24 cm.
Pt. I. Prolegomena. Introduction -- Mathematical preliminaries -- pt. II. State. Online automata: exemplars of "state" -- Finite automata and regular languages -- Applications of the Myhill-Nerode theorem -- Enrichment topics -- pt. III. Encoding. Countability and uncountability: the precursors of "encoding" -- Enrichment topic: "efficient" pairing functions, with applications -- Computability theory -- pt. IV. Nondeterminism. Nondeterministic online automata -- Nondeterministic FAs -- Nondeterminism in computability theory -- Complexity theory.
9780387096384
Computational complexity Logic, Symbolic and mathematical Algorithms Mathematics