Kleene Algebra With Tests for Weighted Programs

Weighted programs generalize probabilistic programs and offer a framework for specifying and encoding mathematical models by means of an algorithmic representation. Kleene algebra with tests is an algebraic formalism based on regular expressions with applications in proving program equivalence. We e...

Full description

Saved in:
Bibliographic Details
Main Author: Sedlar, Igor
Format: Conference Proceeding
Language:English
Subjects:
Algebra
Cognition
Encoding
Kleene algebra with tests
Mathematical models
Probabilistic logic
program equivalence
program semantics
regular programs
Semantics
Systematics
weighted programs
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Weighted programs generalize probabilistic programs and offer a framework for specifying and encoding mathematical models by means of an algorithmic representation. Kleene algebra with tests is an algebraic formalism based on regular expressions with applications in proving program equivalence. We extend the language of Kleene algebra with tests so that it is sufficient to formalize reasoning about a simplified version weighted programs. We introduce relational semantics for the extended language, and we generalize the relational semantics to an appropriate extension of Kleene algebra with tests, called Kleene algebra with weights and tests. We demonstrate by means of an example that Kleene algebra with weights and tests offers a simple algebraic framework for reasoning about equivalence and optimal runs of weighted programs.
ISSN:2378-2226
DOI:10.1109/ISMVL57333.2023.00031