29 citations · 149 across the 31 of their papers we have counts for
31 papers
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…
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…
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…
What do all these Buttons do? Statically Mining Android User Interfaces at Scale
Konstantin Kuznetsov, Chen Fu, Song Gao +3
We introduce FRONTMATTER: a tool to automatically mine both user interface models and behavior of Android apps at a large scale with high precision. Given an app, FRONTMATTER stati…
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…
On the Power of Unambiguity in Büchi Complementation
Yong Li, Moshe Y. Vardi, Lijun Zhang
In this work, we exploit the power of \emph{unambiguity} for the complementation problem of Büchi automata by utilizing reduced run directed acyclic graphs (DAGs) over infinite wor…
Adaptivity and Optimality: A Universal Algorithm for Online Convex Optimization
Guanghui Wang, Shiyin Lu, Lijun Zhang
In this paper, we study adaptive online convex optimization, and aim to design a universal algorithm that achieves optimal regret bounds for multiple common types of loss functions…
Verifying Probabilistic Timed Automata Against Omega-Regular Dense-Time Properties
Hongfei Fu, Yi Li, Jianlin Li +1
Probabilistic timed automata (PTAs) are timed automata (TAs) extended with discrete probability distributions.They serve as a mathematical model for a wide range of applications th…
Finding polynomial loop invariants for probabilistic programs
Yijun Feng, Lijun Zhang, David N. Jansen +2
Quantitative loop invariants are an essential element in the verification of probabilistic programs. Recently, multivariate Lagrange interpolation has been applied to synthesizing…
Distribution-based bisimulation for labelled Markov processes
Pengfei Yang, David N. Jansen, Lijun Zhang
In this paper we propose a (sub)distribution-based bisimulation for labelled Markov processes and compare it with earlier definitions of state and event bisimulation, which both on…
A Novel Learning Algorithm for Büchi Automata based on Family of DFAs and Classification Trees
Yong Li, Yu-Fang Chen, Lijun Zhang +1
In this paper, we propose a novel algorithm to learn a Büchi automaton from a teacher who knows an -regular language. The algorithm is based on learning a formalism named family…
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…
Verify LTL with Fairness Assumptions Efficiently
Yong Li, Lei Song, Yuan Feng +1
This paper deals with model checking problems with respect to LTL properties under fairness assumptions. We first present an efficient algorithm to deal with a fragment of fairness…
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…
Distribution-based Bisimulation and Bisimulation Metric in Probabilistic Automata
Yuan Feng, Lei Song, Lijun Zhang
Probabilistic automata were introduced by Rabin in 1963 as language acceptors. Two automata are equivalent if and only if they accept each word with the same probability. On the ot…
Extending Hybrid CSP with Probability and Stochasticity
Yu Peng, Shuling Wang, Naijun Zhan +1
Probabilistic and stochastic behavior are omnipresent in computer controlled systems, in particular, so-called safety-critical hybrid systems, because of fundamental properties of…
A Simple Probabilistic Extension of Modal Mu-calculus
Wanwei Liu, Lei Song, Ji Wang +1
Probabilistic systems are an important theme in AI domain. As the specification language, the logic PCTL is now the default logic for reasoning about probabilistic properties. In t…
LTLf satisfiability checking
Jianwen Li, Lijun Zhang, Geguang Pu +2
We consider here Linear Temporal Logic (LTL) formulas interpreted over \emph{finite} traces. We denote this logic by LTLf. The existing approach for LTLf satisfiability checking is…
Probably Safe or Live
Joost-Pieter Katoen, Lei Song, Lijun Zhang
This paper presents a formal characterisation of safety and liveness properties à la Alpern and Schneider for fully probabilistic systems. As for the classical setting, it is estab…
Fast LTL Satisfiability Checking by SAT Solvers
Jianwen Li, Geguang Pu, Lijun Zhang +2
Satisfiability checking for Linear Temporal Logic (LTL) is a fundamental step in checking for possible errors in LTL assertions. Extant LTL satisfiability checkers use a variety of…
Polsat: A Portfolio LTL Satisfiability Solver
Jianwen Li, Geguang Pu, Lijun Zhang +3
In this paper we present a portfolio LTL-satisfiability solver, called Polsat. To achieve fast satisfiability checking for LTL formulas, the tool integrates four representative LTL…
When Equivalence and Bisimulation Join Forces in Probabilistic Automata
Yuan Feng, Lijun Zhang
Probabilistic automata were introduced by Rabin in 1963 as language acceptors. Two automata are equivalent if and only if they accept each word with the same probability. On the ot…