- 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