Metraipolis › archive › dc_5ffe37cb0d42
Expressive Power of WSTL Formulas for Learning to Rank — arXiv:2609.22464
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.22464
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T00:55:11.653Z
- SHA-256 of the archived text
ae3e441b8f97af808d0e1c96729bd33afb8a39e3e84c97449c68e2a9cc97966f- Stable URL of this page
https://metraipolis.com/documento/dc_5ffe37cb0d42
How to cite
Expressive Power of WSTL Formulas for Learning to Rank — arXiv:2609.22464 — arXiv (en), https://arxiv.org/abs/2609.22464 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5ffe37cb0d42 (Metraipolis archive dc_5ffe37cb0d42, sha256 ae3e441b8f97af808d0e1c96729bd33afb8a39e3e84c97449c68e2a9cc97966f)
BibTeX
@misc{dc5ffe37cb0d42,
title = {Expressive Power of WSTL Formulas for Learning to Rank — arXiv:2609.22464},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.22464},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5ffe37cb0d42; sha256 ae3e441b8f97af808d0e1c96729bd33afb8a39e3e84c97449c68e2a9cc97966f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.22464. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Weighted Signal Temporal Logic (WSTL) is increasingly used as a scoring function in learning-to-rank problems of trajectories with safety guarantees, where its weighted quantitative semantics serve as a parametrized utility function. Despite the growing interest, prior work only assumes the expressiveness of WSTL formulas and empirically demonstrates its utility in capturing diverse preferences. This work focuses on the correctness of this assumption and asks whether using WSTL formulas as scoring functions is theoretically justified. We formalize two concepts: first, rank-realizability, which asks whether all rankings of a given signal set are achievable by varying weights, and, second, rank-capacity, the maximum signal set size for which the formula is rank-realizable. We propose a Mixed-Integer Linear Program to decide rank-realizability, and derive constructive lower bounds for rank-capacity. Experiments on a robotic navigation task show that while a practical WSTL specification may fail to be rank-realizable on a set with similar trajectories, its rank-capacity exceeds the size of the trajectory set. Analysis of Boolean-equivalent formulas reveals that formula structure affects expressivity and that rank-capacity can be increased without altering qualitative semantics. Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-22 in eess.SY). Categorie arXiv: Systems and Control (eess.SY). Pagina del lavoro: https://arxiv.org/abs/2609.22464 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-09T23:57:37.576Z dalla pagina https://arxiv.org/catchup/eess.SY/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).