Theoretical computer science
- Theory of computation
- - Automata theory
- - - Abstract machine
- - - Turing machine
- - - - Oracle machine
- - - - Register machine
- - - - Non-deterministic Turing machine
- - - - - Probabilistic Turing machine
- - Computability theory
- - - Computable function
- - - - Ackermann function
- - - - Turing-computable function
- - - - μ-recursive function
- - - - Primitive recursive function
- - - Turing completeness
- - - - Esoteric programming language
- - - - Turing tarpit
- - - Decision problem
- - - - Undecidable problem
- - - - - Halting problem
- - - Model of computation
- - - - Decision tree model
- - - - Lambda calculus
- - - - Combinatory logic
- - - - Markov algorithm
- - - - P
- - - - Register machine
- - Computational complexity theory
- - - Time hierarchy theorem
- - - Space hierarchy theorem
- - - Worst-case complexity
- - - Average-case complexity
- - - Generic-case complexity
- - - Reduction (complexity)
- - - Effective method / effective procedure
- - - Complexity class
- - - - Polynomial hierarchy
- - - - Exponential hierarchy
- - - - Grzegorczyk hierarchy
- - - - Arithmetical hierarchy - Wikipedia, the free encyclopedia
- - - - P (complexity)
- - - - P-complete - Wikipedia, the free encyclopedia
- - - - NP (complexity)
- - - - NP-complete
- - - - - Subset sum problem
- - - - PR (complexity)
- - - - BQP
- - - Function problem
- - - Computational problem
- - - Analysis of algorithms
- - - - Big O notation / Big O notation, usada para clasificar algoritmos por como responden a entradas cambiantes
- - - - Correctness (computer science)
- - - - Asymptotic computational complexity
- - - - - Asymptotic analysis
- - - - - Asymptotically optimal algorithm
- - - - - Amortized analysis
- - Model of computation
Formal language theory
- Formation rule
- String (computer science)
- Formal system
- - Metasyntax
- - Programming language
- - Markup language
- Formal grammars
- - Unrestricted grammar
- - - Recursively enumerable language
- - Context-sensitive grammar
- - Indexed grammar
- - Tree-adjoining grammar
- - Context-free grammar
- - Deterministic context-free grammar
- - Nested word
- - Regular grammar
- Formal languages
- - Recursively enumerable language
- - Recursive language
- - Context-sensitive language
- - Indexed language
- - Mildly context-sensitive language
- - Context-free language
- - Deterministic context-free language
- - Regular language
- - Star-free language
- Rational language - Wikipedia, the free encyclope
- Pumping lemma for regular languages
