We present a general methodology of proving the decidability of equational theory of programming language concepts in the framework of second-order algebraic theories. We propose a Haskell-based analysis tool SOL, Second-Order Laboratory, which assists the proofs of confluence and strong normalisation of computation rules derived from second-order algebraic theories. To cover various examples in programming language theory, we combine and extend both syntactical and semantical results of second-order computation in a non-trivial manner. We demonstrate how to prove decidability of various algebraic theories in the literature. It includes the equational theories of monad and lambda-calculi, Plotkin and Power's theory of states, and Stark's theory of pi-calculus.

@article{Hamana17,
  title = {How to prove your calculus is decidable: practical applications of second-order algebraic theories and computation},
  author = {Makoto Hamana},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {1},
  number = {ICFP},
  year = {2017},
  doi = {10.1145/3110266}
}