F. Theory of Computation

• F.0 GENERAL
• F.1 COMPUTATION BY ABSTRACT DEVICES
  • F.1.0 General
  • F.1.1 Models of Computation (see also F.4.1)
    • Automata (e.g., finite, push-down, resource-bounded)
    • Bounded-action devices (e.g., Turing machines, random access machines)
    • Computability theory
    • Relations between models
    • Self-modifying machines (e.g., neural networks)
    • Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
  • F.1.2 Modes of Computation
    • Alternation and nondeterminism
    • Interactive and reactive computation (revised 1998)
    • Online computation (new)
    • Parallelism and concurrency
    • Probabilistic computation
    • Relations among modes (retired since 1998)
    • Relativized computation
  • F.1.3 Complexity Measures and Classes (revised 1998) (see also F.2)
    • Complexity hierarchies
    • Machine-independent complexity (retired since 1998)
    • Reducibility and completeness
    • Relations among complexity classes
    • Relations among complexity measures
  • F.1.m Miscellaneous
• F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY (see also B.6, B.7, F.1.3)
  • F.2.0 General
  • F.2.1 Numerical Algorithms and Problems (see also G.1, G.4, I.1)
    • Computation of transforms (e.g., fast Fourier transform)
    • Computations in finite fields
    • Computations on matrices
    • Computations on polynomials
    • Number-theoretic computations (e.g., factoring, primality testing)
  • F.2.2 Nonnumerical Algorithms and Problems (see also E.2, E.3, E.4, E.5, G.2, H.2, H.3)
    • Complexity of proof procedures
    • Computations on discrete structures
    • Geometrical problems and computations
    • Pattern matching
    • Routing and layout
    • Sequencing and scheduling
    • Sorting and searching
  • F.2.3 Tradeoffs between Complexity Measures (see also F.1.3)
  • F.2.m Miscellaneous
• F.3 LOGICS AND MEANINGS OF PROGRAMS
  • F.3.0 General
  • F.3.1 Specifying and Verifying and Reasoning about Programs (see also D.2.1, D.2.4, D.3.1, E.1)
    • Assertions
    • Invariants
    • Logics of programs
    • Mechanical verification
    • Pre- and post-conditions
    • Specification techniques
  • F.3.2 Semantics of Programming Languages (see also D.3.1)
    • Algebraic approaches to semantics
    • Denotational semantics
    • Operational semantics
    • Partial evaluation (new)
    • Process models (new)
    • Program analysis (new)
  • F.3.3 Studies of Program Constructs (see also D.3.2, D.3.3)
    • Control primitives
    • Functional constructs
    • Object-oriented constructs (new)
    • Program and recursion schemes
    • Type structure
  • F.3.m Miscellaneous
• F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
  • F.4.0 General
  • F.4.1 Mathematical Logic (see also F.1.1, I.2.2, I.2.3, I.2.4)
    • Computability theory
    • Computational logic
    • Lambda calculus and related systems
    • Logic and constraint programming (revised 1998)
    • Mechanical theorem proving
    • Modal logic (new)
    • Model theory
    • Proof theory
    • Recursive function theory
    • Set theory (new)
    • Temporal logic (new)
  • F.4.2 Grammars and Other Rewriting Systems (see also D.3.1)
    • Decision problems
    • Grammar types (e.g., context-free, context-sensitive)
    • Parallel rewriting systems (e.g., developmental systems, L-systems)
    • Parsing
    • Thue systems
  • F.4.3 Formal Languages (see also D.3.1)
    • Algebraic language theory
    • Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)
    • Classes defined by resource-bounded automata (retired since 1998)
    • Decision problems
    • Operations on languages
  • F.4.m Miscellaneous
• F.m MISCELLANEOUS