Canonicity results for mu-calculi: an algorithmic approach

W Conradie, A Craig - Journal of Logic and Computation, 2017 - academic.oup.com
Journal of Logic and Computation, 2017academic.oup.com
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 …
Abstract
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 . 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.
Oxford University Press
以上显示的是最相近的搜索结果。 查看全部搜索结果