An infinitary proof theory is developed for modal logics whose models are coalgebras of polynomial functors on the category of sets. The canonical model method from modal logic is adapted to construct a final coalgebra for any polynomial functor. The states of this final coalgebra are certain “maximal” sets of formulas that have natural syntactic closure properties.
The syntax of these logics extends that of previously developed modal languages for polynomial coalgebras by adding formulas that express the “termination” of certain functions induced by transition paths. A completeness theorem is proven for the logic of functors which have the Lindenbaum property that every consistent set of formulas has a maximal extension. This property is shown to hold if the deducibility relation is generated by countably many inference rules.
A counter-example to completeness is also given. This is a polynomial functor that is not Lindenbaum: it has an uncountable set of formulas that is deductively consistent but has no maximal extension and is unsatisfiable, even though all of its countable subsets are satisfiable. 相似文献
Using automated reasoning techniques, we tackle the niche activity of proving that a program is free from run-time exceptions.
Such a property is particularly valuable in high integrity software, for example, safety- or security-critical applications.
The context for our work is the SPARK Approach for the development of high integrity software. The SPARK Approach provides
a significant degree of automation in proving exception freedom. Where this automation fails, however, the programmer is burdened
with the task of interactively constructing a proof and possibly also having to supply auxiliary program annotations. We minimize
this burden by increasing the automation, through an integration of proof planning and a program analysis oracle. We advocate
a ‘cooperative’ integration, where proof-failure analysis directly constrains the search for auxiliary program annotations.
The approach has been successfully tested on industrial data. 相似文献
This paper describes the integration of a leading SAT solver with Isabelle/HOL, a popular interactive theorem prover. The SAT solver generates resolution-style proofs for (instances of) propositional tautologies. These proofs are verified by the theorem prover. The presented approach significantly improves Isabelle's performance on propositional problems, and furthermore exhibits counterexamples for unprovable conjectures. 相似文献