Hostname: page-component-7b7567c8c-jswmv Total loading time: 0 Render date: 2026-11-15T22:38:21.347Z Has data issue: false hasContentIssue false

How to prove decidability of equational theories with second-order computation analyser SOL

Published online by Cambridge University Press:  24 December 2019

MAKOTO HAMANA*
Affiliation:
Gunma University, Kiryu, Gunma, Japan (e-mail: hamana@cs.gunma-u.ac.jp)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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, i.e. 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 the 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 λ-calculi, Plotkin and Power’s theory of states and bits, and Stark’s theory of π-calculus. We also demonstrate how this methodology can solve the coherence of monoidal categories.

Video Abstract

A video abstract can be found at: https://vimeo.com/365486403

Information

Type
Regular Paper
Copyright
© Cambridge University Press 2019 
Submit a response

Discussions

No Discussions have been published for this article.