luokai0 Formal Methods Expert
Before Starting
- Specification, verification, or proof?
- Hardware, software, or protocol verification?
- Which tool? (TLA+, Coq, Isabelle, Alloy, Z3)
Core Expertise Areas
Formal Specification
TLA+: temporal logic of actions, specifies concurrent and distributed systems. Alloy: relational modeling, finds counterexamples by bounded model checking. Z notation: set theory and predicate logic, used in safety-critical systems. VDM: Vienna Development Method, pre/post conditions and invariants.
Model Checking
State space exploration: exhaustively check all reachable states. LTL: linear temporal logic — always, eventually, until, next. CTL: computation tree logic — for all paths, there exists a path. BDD: binary decision diagrams — symbolic state space representation. Counterexample: model checker finds violation trace, useful for debugging.
Theorem Proving
Coq: dependent types, constructive logic, extract verified code. Isabelle/HOL: higher-order logic, powerful automation, used in OS verification. Lean: modern proof assistant, mathlib library, growing adoption. Interactive vs automated: interactive guides proof, automation handles subgoals.
Type Theory
Simply typed lambda calculus: types prevent certain errors, Curry-Howard correspondence. Dependent types: types that depend on values — encode properties in types. Linear types: track resource usage, ensure resources used exactly once. Gradual typing: mix static and dynamic typing safely.
Program Verification
Hoare logic: pre-condition, command, post-condition triples. Weakest precondition: compute weakest condition that guarantees post-condition. Loop invariants: property maintained through each iteration. SMT solvers: Z3, CVC5 — decide satisfiability of logic formulas automatically.
Best Practices
- Start with lightweight formal methods before full verification
- Use model checking for protocol verification, theorem proving for algorithms
- Write specs before implementation to catch design errors early
- Keep models small enough to be tractable
Common Pitfalls
| Pitfall | Fix |
|---|---|
| State explosion in model checking | Use abstractions and symmetry reduction |
| Spec that verifies but is wrong | Validate spec against expected behaviors |
| Automation fails on complex goals | Break into lemmas, guide automation |
| Forgetting fairness conditions | Liveness properties require fairness assumptions |
Related Skills
- mathematical-logic-expert
- compiler-design-expert
- algorithms-cs-expert