Weighted GKAT: Completeness and Complexity
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913812149436416 |
|---|---|
| author | Van Koevering, Spencer Różowski, Wojciech Silva, Alexandra |
| author_facet | Van Koevering, Spencer Różowski, Wojciech Silva, Alexandra |
| contents | We propose Weighted Guarded Kleene Algebra with Tests (wGKAT), an uninterpreted weighted programming language equipped with branching, conditionals, and loops. We provide an operational semantics for wGKAT using a variant of weighted automata and introduce a sound and complete axiomatization. We also provide a polynomial time decision procedure for bisimulation equivalence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_20385 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Weighted GKAT: Completeness and Complexity Van Koevering, Spencer Różowski, Wojciech Silva, Alexandra Logic in Computer Science Formal Languages and Automata Theory Programming Languages We propose Weighted Guarded Kleene Algebra with Tests (wGKAT), an uninterpreted weighted programming language equipped with branching, conditionals, and loops. We provide an operational semantics for wGKAT using a variant of weighted automata and introduce a sound and complete axiomatization. We also provide a polynomial time decision procedure for bisimulation equivalence. |
| title | Weighted GKAT: Completeness and Complexity |
| topic | Logic in Computer Science Formal Languages and Automata Theory Programming Languages |
| url | https://arxiv.org/abs/2504.20385 |