Completeness of Finitely Weighted Kleene Algebra With Tests

There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

Abstract

Building on \'Esik and Kuich's completeness result for finitely weighted Kleene algebra, we establish relational and language completeness results for finitely weighted Kleene algebra with tests. Similarly as \'Esik and Kuich, we assume that the finite semiring of weights is commutative, partially ordered and zero-bounded, but we also assume that it is integral. We argue that finitely weighted Kleene algebra with tests is a natural framework for equational reasoning about weighted programs in cases where an upper bound on admissible weights is assumed.

Related collections

Author and article information

Journal

Publication date Created: 10 July 2024

Article

DOI: 10.1007/978-3-031-62687-6_14

ArXiV ID: 2407.07570

SO-VID: 1aebb9d9-256e-435c-9b61-c5469f29cd92

License:

http://creativecommons.org/licenses/by/4.0/

History

Custom metadata

Comments Published version: I. Sedl\'ar: Completeness of Finitely Weighted Kleene Algebra with Tests. In: G. Metcalfe, T. Studer, R. de Queiroz (Eds.): Logic, Language, Information, and Computation (WoLLIC 2024), pp. 210-224. Lecture Notes in Computer Science, vol 14672. Springer, Cham, 2024

Categories cs.LO

ScienceOpen disciplines: Theoretical computer science

Data availability:

ScienceOpen disciplines: Theoretical computer science

Comments

Comment on this article

scite_

Smart Citations

Citing PublicationsSupportingMentioningContrasting

View Citations

See how this article has been cited at scite.ai

scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.