Computing Classification System 1998

F.1 COMPUTATION BY ABSTRACT DEVICES ( 0 Dok. )

• F.1.0 General ( 0 Dok. )

• F.1.1 Models of Computation (F.4.1) ( 0 Dok. )
  • F.1.1 Automata (e.g., finite, push-down, resource-bounded)
  • F.1.1 Bounded-action devices (e.g., Turing machines, random access machines)
  • F.1.1 Computability theory
  • F.1.1 Relations between models
  • F.1.1 Self-modifying machines (e.g., neural networks)
  • F.1.1 Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

• F.1.2 Modes of Computation ( 0 Dok. )
  • F.1.2 Alternation and nondeterminism
  • F.1.2 Interactive and reactive computation (REVISED)
  • F.1.2 Online computation
  • F.1.2 Parallelism and concurrency
  • F.1.2 Probabilistic computation
  • F.1.2 Relations among modes**
  • F.1.2 Relativized computation

• F.1.3 Complexity Measures and Classes (F.2) (REVISED) ( 0 Dok. )
  • F.1.3 Complexity hierarchies
  • F.1.3 Machine-independent complexity**
  • F.1.3 Reducibility and completeness
  • F.1.3 Relations among complexity classes
  • F.1.3 Relations among complexity measures

• F.1.m Miscellaneous ( 0 Dok. )