F. Theory of computation

F. Theory of computation : hovedinndeling

• F.0 - Theory of computation - General
• F.1 - Computation by abstract devices
• F.2 - Analysis of algorithms and problem complexity
• F.3 - Logics and meanings of programs
• F.4 - Mathematical logic and formal languages
• F.m - Theory of computation - Miscellaneous

F.0 - Theory of computation - General

F.1 - Computation by abstract devices

F.1.0 - Computation by abstract devices - General

F.1.1 - Models of computation

Automata (e.g. finite, push-down, resource-bounded); Bounded-action devices (e.g. Turing machines, random access machines); Computability theory; Relations among 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; Parallelism and concurrency; Probabilistic computation; Relations among modes; Relativized computation; Online computation;

F.1.3 - Complexity measures and classes

Complexity hierarchies; Machne-independent complexity; Reducibility and completeness; Relations among complexity classes; Relations among complexity measures;

F.1.m - Computation by abstract devices - Miscellaneous

F.2 - Analysis of algorithms and problem complexity

F.2.0 - Analysis of algorithms and problem complexity - General

F.2.1 - Numerical algorithms and problems

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

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 among complexity measures

F.3 - Logics and meanings of programs

F.3.0 - Logics and meanings of programs - General

F.3.1 - Specifying and verifying and reasoning about programs

Assertions; Invariants; Logics of programs; Mechanical verification; Pre- and post-conditions; Specification techniques;

F.3.2 - Semantics of programming languages

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

F.3.3 - Studies of program constructs

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

F.3.m - Logics and meanings of programs - Miscellaneous

F.4 - Mathematical logic and formal languages

F.4.0 - Mathematical logic and formal languages - General

Predicate logic;

F.4.1 - Mathematical logic

Computability theory; Computational logic; Lambda calculus and related systems; Logic and constraint programming; Mechanical theorem proving; Model theory; Proof theory; Recursive function theory; Modal logic; Set theory; Temporal logic;

F.4.2 - Grammars and other rewriting systems

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

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;

F.4.m - Mathematical logic and formal languages - Miscellaneous

F.m - Theory of computation - Miscellaneous