<!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>An Abstract Fixed-point Theorem for Horn Formula Equations</article-title>
      </title-group>
      <contrib-group>
        <aff id="aff0">
          <label>0</label>
          <institution>Institute of Discrete Mathematics and Geometry</institution>
          ,
          <addr-line>TU Wien</addr-line>
          ,
          <country country="AT">Austria</country>
        </aff>
      </contrib-group>
      <abstract>
        <p>interpretation of programs using Galois connections [2]. Our fixed-point theorem allows both new results and simpler proofs of existing results as applications and corollaries. 1. It entails expressibility of the weakest precondition and the strongest postcondition, and thus the partial correctness of an imperative program, in first-order logic with a least fixed-point operator. 2. It allows a generalisation of a result by Ackermann [1] on approximating a second-order formula by first-order formulas in a direction different from the recent generalisation [8]. 3. It allows to obtain a result from a recently introduced approach to automated inductive theorem proving with tree grammars [3] as another straightforward corollary. 4. Since it incorporates abstract interpretation, it permits to considerably simplify the proof of the decidability of affine formula equations originally presented in [5]. This work is rooted in the second author's master's thesis [6]. Some of these results have been presented at the 8th Workshop on Horn Clauses for Verification and Synthesis [4].</p>
      </abstract>
    </article-meta>
  </front>
  <body />
  <back>
    <ref-list>
      <ref id="ref1">
        <mixed-citation>
          1.
          <string-name>
            <surname>Ackermann</surname>
          </string-name>
          , W.:
          <article-title>Untersuchungen u¨ber das Eliminationsproblem der mathematischen Logik</article-title>
          .
          <source>Mathematische Annalen</source>
          <volume>110</volume>
          (
          <issue>1</issue>
          ),
          <fpage>390</fpage>
          -
          <lpage>413</lpage>
          (
          <year>1935</year>
          ). https://doi.org/10.1007/BF01448035
        </mixed-citation>
      </ref>
      <ref id="ref2">
        <mixed-citation>
          2.
          <string-name>
            <surname>Cousot</surname>
            ,
            <given-names>P.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Cousot</surname>
            ,
            <given-names>R.</given-names>
          </string-name>
          :
          <article-title>Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints</article-title>
          . In: Graham,
          <string-name>
            <given-names>R.M.</given-names>
            ,
            <surname>Harrison</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.A.</given-names>
            ,
            <surname>Sethi</surname>
          </string-name>
          ,
          <string-name>
            <surname>R</surname>
          </string-name>
          . (eds.)
          <source>4th ACM Symposium on Principles of Programming Languages</source>
          . pp.
          <fpage>238</fpage>
          -
          <lpage>252</lpage>
          . ACM (
          <year>1977</year>
          ). https://doi.org/10.1145/512950.512973
        </mixed-citation>
      </ref>
      <ref id="ref3">
        <mixed-citation>
          3.
          <string-name>
            <surname>Eberhard</surname>
            ,
            <given-names>S.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Hetzl</surname>
            ,
            <given-names>S.:</given-names>
          </string-name>
          <article-title>Inductive theorem proving based on tree grammars</article-title>
          .
          <source>Annals of Pure and Applied Logic</source>
          <volume>166</volume>
          (
          <issue>6</issue>
          ),
          <fpage>665</fpage>
          -
          <lpage>700</lpage>
          (
          <year>2015</year>
          ). https://doi.org/10.1016/j.apal.
          <year>2015</year>
          .
          <volume>01</volume>
          .002
        </mixed-citation>
      </ref>
      <ref id="ref4">
        <mixed-citation>
          4.
          <string-name>
            <surname>Hetzl</surname>
            ,
            <given-names>S.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Kloibhofer</surname>
            ,
            <given-names>J.:</given-names>
          </string-name>
          <article-title>A fixed point theorem for Horn formula equations</article-title>
          . In: Kafle,
          <string-name>
            <given-names>B.</given-names>
            ,
            <surname>Hojjat</surname>
          </string-name>
          ,
          <string-name>
            <surname>H.</surname>
          </string-name>
          <source>(eds.) 8th Workshop on Horn Clauses for Verification and Synthesis</source>
          (
          <year>2021</year>
          ), available at https://www.sci.unich.it/hcvs21/papers/HCVS 2021 paper
          <article-title>1</article-title>
          .pdf
        </mixed-citation>
      </ref>
      <ref id="ref5">
        <mixed-citation>
          5.
          <string-name>
            <surname>Hetzl</surname>
            ,
            <given-names>S.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Zivota</surname>
            ,
            <given-names>S.</given-names>
          </string-name>
          :
          <article-title>Decidability of affine solution problems</article-title>
          .
          <source>Journal of Logic and Computation</source>
          <volume>30</volume>
          (
          <issue>3</issue>
          ),
          <fpage>697</fpage>
          -
          <lpage>714</lpage>
          (
          <year>2020</year>
          ). https://doi.org/10.1093/logcom/exz033
        </mixed-citation>
      </ref>
      <ref id="ref6">
        <mixed-citation>
          6.
          <string-name>
            <surname>Kloibhofer</surname>
            ,
            <given-names>J.:</given-names>
          </string-name>
          <article-title>A fixed-point theorem for Horn formula equations</article-title>
          .
          <source>Master's thesis</source>
          , TU Wien,
          <string-name>
            <surname>Austria</surname>
          </string-name>
          (
          <year>2020</year>
          )
        </mixed-citation>
      </ref>
      <ref id="ref7">
        <mixed-citation>
          7.
          <string-name>
            <surname>Nonnengart</surname>
            ,
            <given-names>A.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Szalas</surname>
            ,
            <given-names>A.</given-names>
          </string-name>
          :
          <article-title>A Fixpoint Approach to Second-Order Quantifier Elimination with Applications to Correspondence Theory</article-title>
          . In: Orlowska,
          <string-name>
            <surname>E</surname>
          </string-name>
          . (ed.) Logic at Work:
          <article-title>Essays Dedicated to the Memory of Helena Rasiowa, Studies in Fuzziness and Soft Computing</article-title>
          , vol.
          <volume>24</volume>
          , pp.
          <fpage>307</fpage>
          -
          <lpage>328</lpage>
          . Springer (
          <year>1998</year>
          )
        </mixed-citation>
      </ref>
      <ref id="ref8">
        <mixed-citation>
          8.
          <string-name>
            <surname>Wernhard</surname>
            ,
            <given-names>C.</given-names>
          </string-name>
          :
          <article-title>Approximating resultants of existential second-order quantifier elimination upon universal relational first-order formulas</article-title>
          . In: Koopmann,
          <string-name>
            <given-names>P.</given-names>
            ,
            <surname>Rudolph</surname>
          </string-name>
          ,
          <string-name>
            <given-names>S.</given-names>
            ,
            <surname>Schmidt</surname>
          </string-name>
          ,
          <string-name>
            <given-names>R.A.</given-names>
            ,
            <surname>Wernhard</surname>
          </string-name>
          , C. (eds.) Workshop on Second-Order
          <source>Quantifier Elimination and Related Topics (SOQE</source>
          <year>2017</year>
          ).
          <source>CEUR Workshop Proceedings</source>
          , vol.
          <year>2013</year>
          , pp.
          <fpage>82</fpage>
          -
          <lpage>98</lpage>
          (
          <year>2017</year>
          )
        </mixed-citation>
      </ref>
      <ref id="ref9">
        <mixed-citation>
          9.
          <string-name>
            <surname>Wernhard</surname>
            ,
            <given-names>C.</given-names>
          </string-name>
          :
          <article-title>The Boolean Solution Problem from the Perspective of Predicate Logic</article-title>
          . In: Dixon,
          <string-name>
            <given-names>C.</given-names>
            ,
            <surname>Finger</surname>
          </string-name>
          , M. (eds.) 11th
          <source>International Symposium on Frontiers of Combining Systems (FroCoS). Lecture Notes in Computer Science</source>
          , vol.
          <volume>10483</volume>
          , pp.
          <fpage>333</fpage>
          -
          <lpage>350</lpage>
          . Springer (
          <year>2017</year>
          ). https://doi.org/10.1007/978-3-
          <fpage>319</fpage>
          -66167-4 19
        </mixed-citation>
      </ref>
    </ref-list>
  </back>
</article>