Nondeterminism and Language Design in Deep Inference

This thesis studies the design of deep-inference deductive systems. In the systems with deep inference, in contrast to traditional proof-theoretic systems, inference rules can be applied at any depth inside logical expressions. Deep applicability of inference rules provides a rich combinatorial analysis of proofs. Deep inference also makes it possible to design deductive systems that are tailored for computer science applications and otherwise provably not expressible. By applying the inference rules deeply, logical expressions can be manipulated starting from their sub-expressions. This way, we can simulate analytic proofs in traditional deductive formalisms. Furthermore, we can also construct much shorter analytic proofs than in these other formalisms. However, deep applicability of inference rules causes much greater nondeterminism in proof construction. This thesis attacks the problem of dealing with nondeterminism in proof search while preserving the shorter proofs that are available thanks to deep inference. By redesigning the deep inference deductive systems, some redundant applications of the inference rules are prevented. By introducing a new technique which reduces nondeterminism, it becomes possible to obtain a more immediate access to shorter proofs, without breaking certain proof theoretical properties such as cutelimination. Different implementations presented in this thesis allow to perform experiments on the techniques that we developed and observe the performance improvements. Within a computation-as-proof-search perspective, we use deepinference deductive systems to develop a common proof-theoretic language to the two fields of planning and concurrency.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Technische Universität Dresden

Year

2006

Author dc:creator

• Kahramanogullari, Ozan

Contributors dc:contributor

• Hölldobler, Steffen
• Guglielmi, Alessio
• Kirchner, Claude

• Proof Theory
• Nondeterminism
• Deep Infernce
• Proof Search
• Language Design
• Beweistheorie
• Nichtdeterminismus
• Tief Inferenz
• Beweissuche
• Sprachentwurf