User:Dfletter/ACM Mapping to WP/Theory of computation

F. Theory of Computation

F.1 COMPUTATION BY ABSTRACT DEVICES

F.1.1 Models of Computation (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
• Online computation
• Parallelism and concurrency
• Probabilistic computation
• Relations among modes [**]
• Relativized computation

F.1.3 Complexity Measures and Classes (F.2)

• Complexity hierarchies
• Machine-independent complexity [**]
• Reducibility and completeness
• Relations among complexity classes
• Relations among complexity measures

F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY (B.6, B.7, F.1.3)

F.2.1 Numerical Algorithms and Problems (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 (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.3 LOGICS AND MEANINGS OF PROGRAMS

F.3.0 General

F.3.1 Specifying and Verifying and Reasoning about Programs (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 (D.3.1)

• Algebraic approaches to semantics
• Denotational semantics
• Operational semantics
• Partial evaluation
• Process models
• Program analysis

F.3.3 Studies of Program Constructs (D.3.2, D.3.3)

• Control primitives
• Functional constructs
• Object-oriented constructs
• Program and recursion schemes
• Type structure

F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

F.4.1 Mathematical Logic (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
• Mechanical theorem proving
• Modal logic
• Model theory
• Proof theory
• Recursive function theory
• Set theory
• Temporal logic

F.4.2 Grammars and Other Rewriting Systems (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 (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 [**]
• Decision problems
• Operations on languages