Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 1999

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: proof transformations

Sortuj według:

Ogranicz wyniki do:

On intuitionistic proof transformations, their complexity, and application to constructive program synthesis

Egly U., Schmitt S.

Fundamenta Informaticae

1999

Vol. 39, Nr 1,2

59-83

We present a translation of intuitionistic sequent proofs from a multi-succedent calculus LJmc into a single-succedent calculus LJ. The former gives a basis for automated proof search whereas the latter is better suited for proof presentation and program construction from proofs in a system for constructive program synthesis. Well-known translations from the literature have a severe drawback; they use cuts in order to establish the transformation with the undesired consequence that the resulting program term is not intuitive. We establish a transformation based on permutation of inferences and discuss the relevant properties with respect to proof complexity and program terms. As an important result we show that LJ cannot polynomially simulate LJmc (both without the cut rule), even in the propositional fragment.