Canonicity results for mu-calculi: An algorithmic approach

Willem Conradie, Andrew Craig

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


We investigate the canonicity of inequalities of the intuitionistic mu-calculus. The notion of canonicity in the presence of fixed point operators is not entirely straightforward. In the algebraic setting of canonical extensions we examine both the usual notion of canonicity and what we will call tame canonicity. This latter concept has previously been investigated for the classical mu-calculus by Bezhanishvili and Hodkinson. Our approach is in the spirit of Sahlqvist theory. That is, we identify syntactically-defined classes of inequalities, namely the restricted inductive and tame inductive inequalities, which are, respectively, canonical or tame canonical. Our approach is to use an algorithm which processes inequalities with the aim of eliminating propositional variables. The algorithm we introduce is closely related to the algorithms ALBA and mu-ALBA studied by Conradie et al. It is based on a calculus of rewrite rules, the soundness of which rests upon the way in which algebras embed into their canonical extensions and the order-theoretic properties of the latter. We show that the algorithm succeeds on every restricted inductive inequality by means of a so-called proper run, and that this is sufficient to guarantee their canonicity. Likewise, we are able to show that the algorithm succeeds on every tame inductive inequality by means of a so-called tame run. In turn, this guarantees their tame canonicity.

Original languageEnglish
Pages (from-to)705-748
Number of pages44
JournalJournal of Logic and Computation
Issue number3
Publication statusPublished - Apr 2017


  • ALBA algorithm
  • Modal mu-calculus
  • Sahlqvist theory
  • canonical extension
  • canonicity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Arts and Humanities (miscellaneous)
  • Hardware and Architecture
  • Logic


Dive into the research topics of 'Canonicity results for mu-calculi: An algorithmic approach'. Together they form a unique fingerprint.

Cite this