Abstract We consider the problem of controlling a multi-mode system with respect to a safety goal in the Filippov sliding-mode semantics. When the goal can be enforced, we present a symbolic algorithm that enhances the previously known solution. When the goal cannot be enforced, we compare different natural best-effort criteria, identify the most promising one, and design a symbolic algorithm that synthesizes the corresponding myopically optimal control policy. We prove that the synthesized policy enjoys a regularity property known as a tame topology .

Abstract Programs that manipulate tree-shaped data structures often require complex, specialized proofs that are difficult to generalize and automate. This paper introduces a unified, foundational approach to verifying such programs. Central to our approach is the knitted-tree encoding , modeling each program execution as a tree structure capturing input, output, and intermediate states. Leveraging the compositional nature of knitted-trees, we encode these structures as constrained Horn clauses (CHC s), reducing verification to CHC satisfiability. To illustrate our approach, we focus on memory safety and show how it naturally leads to simple, modular invariants.

We introduce a novel approach (COpt) to Fixed-Budget Best-Arm Identification (FBBAI) specifically designed for contexts where both the expected rewards and their variances are unknown a priori. Our methodology starts with the derivation of a general upper bound on the misidentification probability applicable to sub-Gaussian distributions. Based on this theoretical foundation, we develop an algorithm that iteratively solves a non-linear optimization problem over empirical estimators to determine the optimal allocation of the residual sampling budget among the arms. We conducted empirical validation across a range of synthetic distribution classes and a real-world scenario based on the MovieLens dataset. Experimental results demonstrate that COpt consistently achieves superior accuracy compared to established algorithms, including Sequential Halving, VBR, and Gap-EV. Execution time remains within the range of tens of milliseconds, making it suitable for a wide range of applications.

We present a novel automata-based approach to address linear temporal logic modulo theory (LTLfMT) as a specification language for data words. LTLfMT extends LTLf by replacing atomic propositions with quantifier-free multi-sorted first-order formulas interpreted over arbitrary theories. While standard LTLf is reduced to finite automata, we reduce LTLfMT to symbolic data-word automata (SDWAs), whose transitions are guarded by constraints from underlying theories. Both the satisfiability of LTLfMT and the emptiness of SDWAs are undecidable, but the latter can be reduced to a system of constrained Horn clauses, which are supported by efficient solvers and ongoing research efforts. We discuss multiple applications of our approach beyond satisfiability, including model checking and runtime monitoring. Finally, a set of empirical experiments shows that our approach to satisfiability works at least as well as a previous custom solution.

Abstract We study the rational preferences of agents participating in a mechanism whose outcome is a ranking (i.e., a weak order) among participants. We propose a set of self-interest axioms corresponding to different ways for participants to compare rankings. These axioms vary from minimal conditions that most participants can be expected to agree on, to more demanding requirements that apply to specific scenarios. Then, we analyze the theories that can be obtained by combining the previous axioms and characterize their mutual relationships, revealing a rich hierarchical structure. After this broad investigation on preferences over rankings, we consider the case where the mechanism can distribute a fixed monetary reward to the participants in a fair way (that is, depending only on the anonymized output ranking). We show that such mechanisms can induce specific classes of preferences by suitably choosing the assigned rewards, even in the absence of tie breaking.

Solving reachability games is a fundamental problem for the analysis, verification, and synthesis of reactive systems. We consider logical reachability games modulo theories (in short, GMTs), i.e., infinite-state games whose rules are defined by logical formulas over a multi-sorted first-order theory. Our games have an asymmetric constraint: the safety player has at most k possible moves from each game configuration, whereas the reachability player has no such limitation. Even though determining the winner of such a GMT is undecidable, it can be reduced to the well-studied problem of checking the satisfiability of a system of constrained Horn clauses (CHCs), for which many off-the-shelf solvers have been developed. Winning strategies for GMTs can also be computed by resorting to suitable CHC queries. We demonstrate that GMTs can model various relevant real-world games, and that our approach can effectively solve several problems from different domains, using Z3 as the backend CHC solver.

Abstract Reasoning about data structures requires powerful logics supporting the combination of structural and data properties. We define a new logic called Mso-D(Monadic Second-Order logic with Data) as an extension of standard Mso on trees with predicates of the desired data logic. We also define a new class of symbolic data tree automata (Sdtas) to deal with data trees using a simple machine. Mso-D and Sdtas are both Turing-powerful, and their high expressiveness is necessary to deal with interesting data structures. We cope with undecidability by encoding Sdta executions as a system of CHCs (Constrained Horn Clauses), and solving the resulting system using off-the-shelf solvers. We also identify a fragment of Mso-D whose satisfiability can be effectively reduced to the emptiness problem for Sdtas. This fragment is very expressive since it allows us to characterize a variety of data trees from the literature, solving certain infinite-state games, etc. We implement this reduction in a prototype tool that combines an Mso decision procedure over trees (Mona) with a CHC engine (Z3), and use this tool to conduct several experiments, demonstrating the effectiveness of our approach across different problem domains.

We introduce a non-Bayesian variant of Thompson sampling whose belief is based on the Central Limit Theorem. As such, it is a parameter-less and prior-free algorithm for the stochastic multi-armed bandit problem. We analyze its asymptotical behavior by proving that it is greedy in the limit of infinite exploration. Further, we empirically evaluate its performance in the fixed-budget best-arm identification problem. In a suite of empirical tests, including both bounded and unbounded reward distributions, our approach exhibits in many cases the lowest misidentification rate among the state-of-the-art algorithms.

Bayesian Preference Elicitation (PE) is an active learning technique aimed at discovering users’ preferences through a suitable sequence of queries. One of its prominent applications consists in providing personalized product recommendations in e-Commerce scenarios. In these settings, where catalogs may contain hundreds or thousands of different products, it becomes crucial to find a good trade-off between recommendation quality and computational cost.In this paper we introduce QUEST, a highly configurable PE framework supporting arbitrary value functions on multi-attribute product domains. We use QUEST to compare established and novel query selection methodologies to achieve real-time user interaction, while preserving recommendation quality. In particular, the experimental assessment shows that a novel uncertainty-based query selection strategy outperforms the largely used value-of-information (VOI) both in accuracy and execution time.

Abstract We consider tournaments played by a set of players in order to establish a ranking among them. We introduce the notion of irrelevant match, as a match that does not influence the ultimate ranking of the involved parties. After discussing the basic properties of this notion, we seek out tournaments that have no irrelevant matches, focusing on the class of tournaments where each player challenges each other exactly once. We prove that tournaments with a static schedule and at least five players always include irrelevant matches. Conversely, dynamic schedules for an arbitrary number of players can be devised that avoid irrelevant matches, at least for one of the players involved in each match. Finally, we prove by computational means that there exist tournaments where all matches are relevant to both players, at least up to eight players.

We study the rational preferences of agents participating in a mechanism whose outcome is a weak order among participants. We propose a set of self-interest axioms and characterize the mutual relationships between all subsets thereof. We then assume that the mechanism can assign monetary rewards to the agents, in a way that is consistent with the weak order. We show that the mechanism can induce specific classes of preferences by suitably choosing the assigned rewards, even in the absence of tie breaking.

Nonmonotonic inferences are not yet supported by Description Logic technology, although their potential usefulness is widely recognized. Lack of support to nonmonotonic reasoning is due to a number of issues related to expressiveness, computational complexity, and optimizations. This work contributes to the practical support of nonmonotonic reasoning in description logics by introducing a new semantics designed to address knowledge engineering needs. The formalism is validated through extensive comparison with the other nonmonotonic DLs, and systematic scalability tests.

We consider the problem of computing the controllable region of a Linear Hybrid Automaton with controllable and uncontrollable transitions, w.r.t. a reachability objective. We provide an algorithm for the finite-horizon version of the problem, based on computing the set of states that must reach a given non-convex polyhedron while avoiding another one, subject to a polyhedral constraint on the slope of the trajectory. Experimental results are presented, based on an implementation of the proposed algorithm on top of the tool SpaceEx.

The classical model of Markov decision processes with costs or rewards, while widely used to formalize optimal decision making, cannot capture scenarios where there are multiple objectives for the agent during the system evolution, but only one of these objectives gets actualized upon termination. We introduce the model of Markov decision processes with alternative objectives (MDPAO) for formalizing optimization in such scenarios. To compute the strategy to optimize the expected cost/reward upon termination, we need to figure out how to balance the values of the alternative objectives. This requires analysis of the underlying infinite-state process that tracks the accumulated values of all the objectives. While the decidability of the problem of computing the exact optimal strategy for the general model remains open, we present the following results. First, for a Markov chain with alternative objectives, the optimal expected cost/reward can be computed in polynomial-time. Second, for a single-state process with two actions and multiple objectives we show how to compute the optimal decision strategy. Third, for a process with only two alternative objectives, we present a reduction to the minimum expected accumulated reward problem for one-counter MDPs, and this leads to decidability for this case under some technical restrictions. Finally, we show that optimal cost/reward can be approximated up to a constant additive factor for the general problem.

We analyze the properties of differentiable trajectories subject to a constant differential inclusion which constrains the first derivative to belong to a given convex polyhedron. We present the first exact algorithm that computes the set of points from which there is a trajectory that reaches a given polyhedron while avoiding another (possibly non-convex) polyhedron. We discuss the connection with (Linear) Hybrid Automata and in particular the relationship with the classical algorithm for reachability analysis for Linear Hybrid Automata.

We consider the problem of computing the controllable region of a Linear Hybrid Automaton with controllable and uncontrollable transitions, w.r.t. a reachability objective. We provide a semi-algorithm for the problem, by proposing the first algorithm in the literature for computing the set of states that must reach a given polyhedron while avoiding another one, subject to a polyhedral constraint on the slope of the trajectory. Experimental results are presented, based on an implementation of the proposed algorithm on top of the tool PHAVer.

The research on low-complexity nonmonotonic description logics recently identified a fragment of EL with bottom, supporting defeasible inheritance with overriding, where reasoning can be carried out in polynomial time. We contribute to that framework by supporting more axiom schemata and all the concept constructors of EL++ without increasing asymptotic complexity. Moreover, we show that all the syntactic restrictions we adopt are necessary by proving several coNP-hardness results.

We analyze the complexity of reasoning in EL with defeasible inclusions and extensions thereof. The results by Bonatti et al., 2009a are extended by proving tight lower complexity bounds and by relaxing the syntactic restrictions adopted there. We further extend the old framework by supporting arbitrary priority relations.

Recently, temporal logics such as μ-calculus and Computational Tree Logic, CTL, augmented with graded modalities have received attention from the scientific community, both from a theoretical side and from an applicative perspective. In both these se

We extend the classical system relations of trace inclusion, trace equivalence, simulation, and bisimulation to a quantitative setting in which propositions are interpreted not as boolean values, but as elements of arbitrary metric spaces. Trace inclusion and equivalence give rise to asymmetrical and symmetrical linear distances, while simulation and bisimulation give rise to asymmetrical and symmetrical branching distances. We study the relationships among these distances and we provide a full logical characterization of the distances in terms of quantitative versions of LTL and mu-calculus. We show that, while trace inclusion (respectively, equivalence) coincides with simulation (respectively, bisimulation) for deterministic boolean transition systems, linear and branching distances do not coincide for deterministic metric transition systems. Finally, we provide algorithms for computing the distances over finite systems, together with a matching lower complexity bound.

We present the tool Ticc ( Tool for Interface Compatibility and Composition ). In Ticc , a component interface describes both the behavior of a component, and the component’s assumptions on the environment’s behavior. Ticc can check the compatibility of such interfaces, and analyze their emergent behavior, via a symbolic implementation of game-theoretic algorithms. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Multithreaded programs coordinate their interaction through synchronization primitives like mutexes and semaphores, which are managed by an OS-provided resource manager. We propose algorithms for the automatic construction of code-aware resource managers for multithreaded embedded applications. Such managers use knowledge about the structure and resource usage (mutex and semaphore usage) of the threads to guarantee deadlock freedom and progress while managing resources in an efficient way. Our algorithms compute managers as winning strategies in certain infinite games, and produce a compact code description of these strategies. We have implemented the algorithms in the tool Cynthesis. Given a multithreaded program in C, the tool produces C~code implementing a code-aware resource manager. We show in experiments that Cynthesis produces compact resource managers within a few minutes on a set of embedded benchmarks with up to 6 threads.

The rapid development of complex and safety-critical systems requires the use of reliable verification methods and tools for system design (synthesis). Many systems of interest are reactive, in the sense that their behavior depends on the interaction with the environment. A natural framework to model them is a two-player game: the system versus the environment. In this context, the central problem is to determine the existence of a winning strategy according to a given winning condition. We focus on real-time systems, and choose to model the related game as a nondeterministic timed automaton. We express winning conditions by formulas of the branching-time temporal logic TCTL. While timed games have been studied in the literature, timed games with dense-time winning conditions constitute a new research topic. The main result of this paper is an exponential-time algorithm to check for the existence of a winning strategy for TCTL games where equality is not allowed in the timing constraints. Our approach consists on translating to timed tree automata both the game graph and the winning condition, thus reducing the considered decision problem to the emptiness problem for this class of automata. The proposed algorithm matches the known lower bound on timed games. Moreover, if we relax the limitation we have placed on the timing constraints, the problem becomes undecidable.