Discounted-sum inclusion (DS-inclusion, in short) formalizes the goal of comparing quantitative dimensions of systems such as cost, resource consumption, and the like, when the mode of aggregation for the quantitative dimension is discounted-sum aggregation. Discounted-sum comparator automata, or DS-comparators in short, are Buechi automata
that read two in nite sequences of weights synchronously and relate their discounted-sum. Recent empirical investigations have shown that while DS-comparators enable competitive algorithms for DS-inclusion, they still suffer from the scalability bottleneck of Bueuchi operations. Motivated by the connections between discounted-sum and Buechi automata,
this paper undertakes an investigation of language-theoretic properties of DS-comparators in order to mitigate the challenges of Buechi DS-comparators to achieve improved scalability of DS-inclusion. Our investigation uncovers that DS-comparators possess safety and co-safety language-theoretic properties. As a result, they enable reductions based on subset construction-based methods as opposed to higher complexity Buechi complementation, yielding tighter worst-case complexity and improved empirical scalability for DS-inclusion.
more »
« less
Safety-Aware Preference-Based Learning for Safety-Critical Control
- Award ID(s):
- 1932091
- NSF-PAR ID:
- 10357600
- Date Published:
- Journal Name:
- 4th Annual Learning for Dynamics and Control Conference, PMLR
- Volume:
- 168
- Page Range / eLocation ID:
- 1020-1033
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
