Stochastic interaction and linear logic
Lists
Only you see this
Abstract
We present stochastic interactive semantics for propositional linear logic without modalities. The framework is based on interactive protocols considered in computational complexity theory, in which a prover with unlimited power interacts with a verifier that can only toss fair coins or perform simple tasks when presented with the given formula or with subsequent messages from the prover. The additive conjunction &, is described as random choice, which reflects the intuitive idea that the verifier can perform only “random spot checks”. This stochastic interactive semantic framework is shown to be sound and complete. Furthermore, the prover's winning strategies are basically proofs of the given formula. In this framework the multiplicative and additive connectives of linear logic are described by means of probabilistic operators, giving a new basis for intuitive reasoning about linear logic and a potential new tool in automated deduction.
BibTeX
@inproceedings{lincoln1995stochastic,
author = {Patrick Lincoln and John C. Mitchell and Andre Scedrov},
title = {{Stochastic interaction and linear logic}},
booktitle = {Cambridge},
year = {1995},
doi = {10.1017/cbo9780511629150.008},
}Loading related content...