6 citations · 17 across the 16 of their papers we have counts for
17 papers
Synthesizing Probabilistic Saturating Counters with Differentially Private Formal Guarantees
Zhiming Chi, Lutan Zhao, Depeng Liu +8
Branch predictors improve instruction-level parallelism in modern processors and are commonly modeled using saturating counters. However, classical saturating counters are determin…
PAC Approximation and DIRECT Optimization for Parametric Markov Models
Zhiming Chi, Ying Liu, Andrea Turrini +2
In this paper, we consider the parameter synthesis and optimization problem for parametric Markov decision processes (pMDPs), the extension of classical MDPs where exact probabilit…
Resource-Constrained Robotic Planning in the face of Mixed Uncertainty
Yihao Yin, Pian Yu, Andrea Turrini +3
Robots operate under significant uncertainty, from quantifiable noise to unquantifiable unknowns, and must account for strict operational constraints, such as limited resources. In…
Efficient Decomposition Identification of Deterministic Finite Automata from Examples
Junjie Meng, Jie An, Yong Li +4
The identification of deterministic finite automata (DFAs) from labeled examples is a cornerstone of automata learning, yet traditional methods focus on learning monolithic DFAs, w…
Scenario Approach for Parametric Markov Models
Ying Liu, Andrea Turrini, Moritz Hahn +2
In this paper, we propose an approximating framework for analyzing parametric Markov models. Instead of computing complex rational functions encoding the reachability probability a…
A Symbolic Algorithm for the Case-Split Rule in Solving Word Constraints with Extensions (Technical Report)
Yu-Fang Chen, Vojtěch Havlena, Ondřej Lengál +1
Case split is a core proof rule in current decision procedures for the theory of string constraints. Its use is the primary cause of the state space explosion in string constraint…
Modular Mix-and-Match Complementation of Büchi Automata (Technical Report)
Vojtěch Havlena, Ondřej Lengál, Yong Li +2
Complementation of nondeterministic Büchi automata (BAs) is an important problem in automata theory with numerous applications in formal verification, such as termination analysis…
Divide-and-Conquer Determinization of Büchi Automata based on SCC Decomposition
Yong Li, Andrea Turrini, Weizhi Feng +2
The determinization of a nondeterministic Büchi automaton (NBA) is a fundamental construction of automata theory, with applications to probabilistic verification and reactive synth…
On the Power of Finite Ambiguity in Büchi Complementation
Weizhi Feng, Yong Li, Andrea Turrini +2
In this work, we exploit the power of \emph{finite ambiguity} for the complementation problem of Büchi automata by using reduced run directed acyclic graphs (DAGs) over infinite wo…
Proving Non-Inclusion of Büchi Automata based on Monte Carlo Sampling
Yong Li, Andrea Turrini, Xuechao Sun +1
The search for a proof of correctness and the search for counterexamples (bugs) are complementary aspects of verification. In order to maximize the practical use of verification to…
Model Checking Applied to Quantum Physics
Ji Guan, Yuan Feng, Andrea Turrini +1
Model checking has been successfully applied to verification of computer hardware and software, communication systems and even biological systems. In this paper, we further push th…
Multi-objective Robust Strategy Synthesis for Interval Markov Decision Processes
Ernst Moritz Hahn, Vahid Hashemi, Holger Hermanns +2
Interval Markov decision processes (IMDPs) generalise classical MDPs by having interval-valued transition probabilities. They provide a powerful modelling tool for probabilistic sy…
Compositional Reasoning for Interval Markov Decision Processes
Vahid Hashemi, Holger Hermanns, Andrea Turrini
Model checking probabilistic CTL properties of Markov decision processes with convex uncertainties has been recently investigated by Puggelli et al. Such model checking algorithms…
Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games
Ernst Moritz Hahn, Sven Schewe, Andrea Turrini +1
2.5 player parity games combine the challenges posed by 2.5 player reachability games and the qualitative analysis of parity games. These two types of problems are best approached…
An Efficient Synthesis Algorithm for Parametric Markov Chains Against Linear Time Properties
Yong Li, Wanwei Liu, Andrea Turrini +2
In this paper, we propose an efficient algorithm for the parameter synthesis of PLTL formulas with respect to parametric Markov chains. The PLTL formula is translated to an almost…
Cost Preserving Bisimulations for Probabilistic Automata
Andrea Turrini, Holger Hermanns
Probabilistic automata constitute a versatile and elegant model for concurrent probabilistic systems. They are equipped with a compositional theory supporting abstraction, enabled…
Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time
Holger Hermanns, Andrea Turrini
Deciding in an efficient way weak probabilistic bisimulation in the context of Probabilistic Automata is an open problem for about a decade. In this work we close this problem by p…