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

F. Theory of Computation Wiki Category:Theory of computation

F.1 COMPUTATION BY ABSTRACT DEVICES

F.1.0 General

===F.1.1 Models of Computation=== (F.4.1) Wiki category:Computational models

• 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)

Wiki category:Cellular automata

F.1.2 Modes of Computation

Wiki category:Computational models

• Alternation and nondeterminism
• Interactive and reactive computation
• Online computation
• Parallelism and concurrency
• Probabilistic computation
• Relativized computation

===F.1.3 Complexity Measures and Classes=== (F.2) Wiki category:Category:Computational complexity theory

• Complexity hierarchies
• Reducibility and completeness
• Relations among complexity classes
• Relations among complexity measures

F.1.m Miscellaneous

==F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY== (B.6, B.7, F.1.3) Wiki category:analysis of algorithms

F.2.0 General

===F.2.1 Numerical Algorithms and Problems === (G.1, G.4, I.1) Wiki Category:Numerical analysis, Wiki category:Algorithms, category:Computer algebra

• 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) Wiki category:Algorithms

• Complexity of proof procedures
• Computations on discrete structures
• Geometrical problems and computations
• Pattern matching
• Routing and layout
• Sequencing and scheduling
• Sorting and searching

Wiki Category:Sort_algorithms, Wiki Category:Search_algorithms

===F.2.3 Tradeoffs between Complexity Measures=== (F.1.3) Wiki category:Analysis of algorithms

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) Wiki category:Formal methods

• 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) Wiki category:Programming constructs

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

F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

F.4.0 General

===F.4.1 Mathematical Logic=== (F.1.1, I.2.2, I.2.3, I.2.4) Wiki category:Mathematical logic

• 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) Wiki category:Formal languages

• 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) Wiki category:Formal languages

• Algebraic language theory
• Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)
• Decision problems
• Operations on languages