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. 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. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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