
<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
One concern of theoretical computer science is to prove the correctness of algorithms, for example the implementation of datastructures that are at the core of almost all programs. This becomes especially complicated when concurrency is involved in a non-trivial way, such that multiple parts of memory that logically belong together are modified in parallel. Proof Assistants are computer programs that enable logical reasoning in a strict formal proof system. Developing proofs inside a such a proof assistant requires extreme rigour. As long as your definitions are not flawed, it is practically impossible to miss edge cases. The proof assistant we use is called Coq. Coq is not readily usable to reason about programs that use mutable resources, but the Iris project has built a framework inside Coq that offers a convenient language and toolbox for this. Iris uses separation logic and modal logic to reason about memory, concurrency, and potentially non-terminating recursion. Contributions: Circular lists in Iris We formalize a circular doubly linked list in Coq/Iris using separation logic. We only verified synchronous list operations. This chapter demonstrates the use of separation logic to reason about locations stored on a heap. To our knowledge this is the first interactive verification of a circular list using separation logic. Deduction rules of ��� We study the model of plain step-indexed propositions without resources, a basic interpretation of the ��� modality. We determine a complete set of deductions, and formalize an algorithm that checks a finite number of potential counterexamples in Coq, proving decidability and completeness.
separation logic, formal verification, modal logic
separation logic, formal verification, modal logic
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
views | 121 | |
downloads | 21 |