A Complete Inference System for Skip-free Guarded Kleene Algebra with Tests
| Authors |
|
|---|---|
| Publication date | 2023 |
| Host editors |
|
| Book title | Programming Languages and Systems |
| Book subtitle | 32nd European Symposium on Programming, ESOP 2023, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023 : proceedings |
| ISBN |
|
| ISBN (electronic) |
|
| Series | Lecture Notes in Computer Science |
| Event | 32nd European Symposium on Programming |
| Pages (from-to) | 309-226 |
| Number of pages | 28 |
| Publisher | Cham: Springer |
| Organisations |
|
| Abstract | Guarded Kleene Algebra with Tests (GKAT) is a fragment of Kleene Algebra with Tests (KAT) that was recently introduced to reason efficiently about imperative programs. In contrast to KAT, GKAT does not have an algebraic axiomatization, but relies on an analogue of Salomaa’s axiomatization of Kleene Algebra. In this paper, we present an algebraic axiomatization and prove two completeness results for a large fragment of GKAT consisting of skip-free programs. |
| Document type | Conference contribution |
| Language | English |
| Published at | https://doi.org/10.48550/arXiv.2301.11301 https://doi.org/10.1007/978-3-031-30044-8_12 |
| Downloads |
978-3-031-30044-8_12
(Final published version)
|
| Permalink to this page | |
