# Up-To Techniques for Weighted Systems (Extended Version)

Source: [Up-To Techniques for Weighted Systems (Extended Version)](<https://www.sota2.com/research/paper/68fa631c1e209131ce9fcdd3>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T20:33:20.017Z

Authors: Filippo Bonchi, Barbara K\\"onig, Sebastian K\\"upper

Published: 2017-01-18T10:33:52.000Z

## Abstract

We show how up-to techniques for (bi-)similarity can be used in the setting of weighted systems. The problems we consider are language equivalence, language inclusion and the threshold problem (also known as universality problem) for weighted automata. We build a bisimulation relation on the fly and work up-to congruence and up-to similarity. This requires to determine whether a pair of vectors (over a semiring) is in the congruence closure of a given relation of vectors. This problem is considered for rings and l-monoids, for the latter we provide a rewriting algorithm and show its confluence and termination. We then explain how to apply these up-to techniques to weighted automata and provide runtime results.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1701.05001>)

[PDF](<https://arxiv.org/pdf/1701.05001.pdf>)
