Computer · Part C - Software, Algorithms and Computation · Major topic 10 of 39
Theory of Computation, Formal Languages and Verification
The mathematical limits of computation, language recognition, formal specifications and confidence in program behavior.
128 items insideCOM-10
Also look at: Geography: Human Geography — 10. Language GeographyReasoning: Reasoning Skills RoadmapScience & Technology: Computer Architecture, Operating Systems, Programming and Software SystemsArt & Culture: Languages and Scripts of India
- 1
Historical evolution — key dates
- Gödel’s incompleteness results reshape the landscape of formal systems.1931
- Turing and Church formalize computability in complementary ways.1936
- Automata and formal-language models develop alongside switching and communication theory.1940s-1950s
- Chomsky’s hierarchy of grammars helps organize formal languages.1956
- Complexity classes, program verification and logic-based specification mature.1960s-1970s
- Model checking, SAT solving and proof assistants become practical verification tools.1980s-2000s
- Formal methods are applied to cryptography, protocols, safety-critical systems and verified software.2010s-2020s
- 2
Formal foundations
- Alphabet; symbol; string; language; concatenation; closure; language operation; grammar; production rule; derivation
10 more points
- Alphabet
- Symbol
- String
- Language
- Concatenation
- Closure
- Language operation
- Grammar
- Production rule
- Derivation
- Regular expressions; regular language; context-free language; context-sensitive and unrestricted grammars
4 more points
- Regular expressions
- Regular language
- Context-free language
- Context-sensitive and unrestricted grammars
- Alphabet; symbol; string; language; concatenation; closure; language operation; grammar; production rule; derivation
- 3
Automata and recognition
- Deterministic/non-deterministic finite automata; epsilon transitions; regular-expression equivalence
3 more points
- Deterministic/non-deterministic finite automata
- Epsilon transitions
- Regular-expression equivalence
- Pushdown automata; stack; context-free language; parse tree; ambiguity
5 more points
- Pushdown automata
- Stack
- Context-free language
- Parse tree
- Ambiguity
- Turing machine; tape; state; transition function; multi-tape model; universal machine
6 more points
- Turing machine
- Tape
- State
- Transition function
- Multi-tape model
- Universal machine
- Deterministic/non-deterministic finite automata; epsilon transitions; regular-expression equivalence
- 4
Computability and decidability
- Computable function; recognizer vs decider; halting problem; reduction; undecidable problem
5 more points
- Computable function
- Recognizer vs decider
- Halting problem
- Reduction
- Undecidable problem
- Church-Turing thesis; universal computation; diagonalization; Rice’s theorem; limits of formal reasoning
5 more points
- Church-Turing thesis
- Universal computation
- Diagonalization
- Rice’s theorem
- Limits of formal reasoning
- Computable function; recognizer vs decider; halting problem; reduction; undecidable problem
- 5
Complexity theory
- Time/space classes; P; NP; co-NP; NP-complete; NP-hard; polynomial reduction
7 more points
- Time/space classes
- P
- NP
- Co-NP
- NP-complete
- NP-hard
- Polynomial reduction
- Randomized classes; approximation; parameterized complexity; space hierarchy; circuit complexity; quantum complexity overview
6 more points
- Randomized classes
- Approximation
- Parameterized complexity
- Space hierarchy
- Circuit complexity
- Quantum complexity overview
- Time/space classes; P; NP; co-NP; NP-complete; NP-hard; polynomial reduction
- 6
Logic for computer science
- Propositional/predicate logic; temporal logic; Hoare logic; modal logic; type logic; fixed-point logic
6 more points
- Propositional/predicate logic
- Temporal logic
- Hoare logic
- Modal logic
- Type logic
- Fixed-point logic
- SAT/SMT; theorem proving; resolution; unification; constraint solving; satisfiability and model construction
6 more points
- SAT/SMT
- Theorem proving
- Resolution
- Unification
- Constraint solving
- Satisfiability and model construction
- Propositional/predicate logic; temporal logic; Hoare logic; modal logic; type logic; fixed-point logic
- 7
Program specification and proof
- Preconditions/postconditions; invariants; contracts; refinement; weakest precondition; termination proof
6 more points
- Preconditions/postconditions
- Invariants
- Contracts
- Refinement
- Weakest precondition
- Termination proof
- Hoare triples; separation logic; ownership/borrowing reasoning; functional correctness; non- functional properties
5 more points
- Hoare triples
- Separation logic
- Ownership/borrowing reasoning
- Functional correctness
- Non- functional properties
- Preconditions/postconditions; invariants; contracts; refinement; weakest precondition; termination proof
- 8
Verification methods
- Static analysis; symbolic execution; abstract interpretation; model checking; equivalence checking; proof assistants
6 more points
- Static analysis
- Symbolic execution
- Abstract interpretation
- Model checking
- Equivalence checking
- Proof assistants
- Test generation; coverage-guided fuzzing; property-based tests; runtime verification; proof- carrying code
5 more points
- Test generation
- Coverage-guided fuzzing
- Property-based tests
- Runtime verification
- Proof- carrying code
- Static analysis; symbolic execution; abstract interpretation; model checking; equivalence checking; proof assistants
- 9
Reliability and assurance
- Safety cases; hazard analysis; fault trees; formal requirements; traceability; independent verification/validation
6 more points
- Safety cases
- Hazard analysis
- Fault trees
- Formal requirements
- Traceability
- Independent verification/validation
- Trusted computing base; assurance levels; review evidence; reproducible proof and tool limitations
4 more points
- Trusted computing base
- Assurance levels
- Review evidence
- Reproducible proof and tool limitations
- Safety cases; hazard analysis; fault trees; formal requirements; traceability; independent verification/validation
