<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta />
    <article-meta>
      <title-group>
        <article-title>Cut Elimination and Second Order Quantifier Elimination (Abstract of Tutorial)</article-title>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <string-name>Alessandra Palmigiano with Giuseppe Greco</string-name>
          <xref ref-type="aff" rid="aff0">0</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Minghui Ma</string-name>
          <xref ref-type="aff" rid="aff0">0</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Apostolos Tzimoulis</string-name>
          <xref ref-type="aff" rid="aff0">0</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Zhiguang Zhao</string-name>
          <xref ref-type="aff" rid="aff0">0</xref>
        </contrib>
        <aff id="aff0">
          <label>0</label>
          <institution>Delft University of Technology</institution>
          ,
          <country country="NL">Netherlands</country>
        </aff>
      </contrib-group>
      <fpage>19</fpage>
      <lpage>20</lpage>
      <abstract>
        <p>Display calculi, pioneered by Belnap [1], are a proof-theoretic framework generalizing Gentzen's sequent calculi, which have succeeded in endowing a large class of modal logics with cut-free sequent calculi in a uniform and modular way. The robustness and modularity of display calculi are rooted in a general methodology for proving cut-elimination, which identifies conditions on the design of sequent calculi which guarantee the success of a certain uniform strategy for syntactic cut elimination. Recently, systematic connections have been established between algorithmic correspondence theory, well known from the area of modal logic, and the theory of display calculi. These connections originate from some seminal observations made by Kracht [5], in the context of his characterization of the modal axioms which can be effectively transformed into 'analytic' structural rules of display calculi. In this context, a rule is 'analytic' if adding it to a display calculus preserves Belnap's cut-elimination theorem. The present tutorial illustrates these connections. Specifically, after introducing (proper) display calculi and discussing the uniform strategy for their cut elimination, I will discuss how the two main tools of unified correspondence theory [3], [2] (namely, (a) the ALBA algorithm for second order quantifier elimination, and (b) the syntactically defined class of inductive inequalities in each logical/algebraic signature of normal distributive lattice expansions) can be used to produce analytic calculi for a certain subclass of inductive formulas (the analytic inductive inequalities), and to exhaustively characterize this subclass as the class of the 'properly displayable' logics. Time permitting, I will also discuss how the methodology of multi-type calculi [4] can be used to circumvent this exhaustive characterization, and export these techniques also to non analytic logics.</p>
      </abstract>
    </article-meta>
  </front>
  <body />
  <back>
    <ref-list>
      <ref id="ref1">
        <mixed-citation>
          3.
          <string-name>
            <given-names>W.</given-names>
            <surname>Conradie</surname>
          </string-name>
          and
          <string-name>
            <given-names>A.</given-names>
            <surname>Palmigiano</surname>
          </string-name>
          .
          <article-title>Algorithmic correspondence and canonicity for non-distributive logics</article-title>
          . Submitted.
          <source>ArXiv preprint 1603</source>
          .08515.
        </mixed-citation>
      </ref>
      <ref id="ref2">
        <mixed-citation>
          4.
          <string-name>
            <given-names>S.</given-names>
            <surname>Frittella</surname>
          </string-name>
          ,
          <string-name>
            <given-names>G.</given-names>
            <surname>Greco</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Kurz</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Palmigiano</surname>
          </string-name>
          , and
          <string-name>
            <given-names>V.</given-names>
            <surname>Sikimi</surname>
          </string-name>
          <article-title>´c. Multi-type sequent calculi</article-title>
          . In
          <string-name>
            <surname>M. Z. A. Indrzejczak</surname>
          </string-name>
          and J. Kaczmarek, editors,
          <source>Proceedings of Trends in Logic XIII</source>
          , pages
          <fpage>81</fpage>
          -
          <lpage>93</lpage>
          . Lodz University Press,
          <year>2014</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref3">
        <mixed-citation>
          5.
          <string-name>
            <given-names>M.</given-names>
            <surname>Kracht</surname>
          </string-name>
          .
          <article-title>Power and weakness of the modal display calculus</article-title>
          .
          <source>In Proof theory of modal logic</source>
          , volume
          <volume>2</volume>
          of Applied Logic Series, pages
          <fpage>93</fpage>
          -
          <lpage>121</lpage>
          . Kluwer,
          <year>1996</year>
          .
        </mixed-citation>
      </ref>
    </ref-list>
  </back>
</article>