59 citations · 68 across the 20 of their papers we have counts for
22 papers
From Ramsey-Based to Congruence-Based Constructions for Büchi Complementation
Yih-Kuen Tsay, Moshe Y. Vardi
The very first construction by J. Richard Büchi himself for complementing a Büchi automaton relies on a fundamental lemma about the division of an arbitrary infinite word into cons…
The Stochastic Target Discounted-Sum Problem
Nathalie Bertrand, Pranav Ghorpade, Senthil Rajasekaran +2
The target discounted-sum problem (TDS) asks, given a finite integer alphabet , a rational discount factor , and a rational target , whether some infinite sequence over $Σ…
Categorizer Automata for Discounted-Sum Payoffs
Nathalie Bertrand, Pranav Ghorpade, Senthil Rajasekaran +2
Categorizing continuous data into discrete bins is a fundamental operation in artificial intelligence. We introduce the categorizer automaton, a deterministic automaton that reads…
Modeling Concurrent Multi-Agent Systems
Senthil Rajasekaran, Moshe Y. Vardi
Recent work in the field of multi-agent systems has sought to use techniques and concepts from the field of formal methods to provide rigorous theoretical analysis and guarantees o…
TIDE: A Trace-Informed Depth-First Exploration for Planning with Temporally Extended Goals
Yuliia Suprun, Khen Elimelech, Lydia E. Kavraki +1
Task planning with temporally extended goals (TEGs) is a critical challenge in AI and robotics, enabling agents to achieve complex sequences of objectives over time rather than add…
Dynamic Boolean Synthesis with Zero-suppressed Decision Diagrams
Yi Lin, Moshe Y. Vardi
Motivated by functional synthesis in sequential circuit construction and quantified boolean formulas (QBF), boolean synthesis serves as one of the core problems in Formal Methods.…
Thinking Out of the Box: Hybrid SAT Solving by Unconstrained Continuous Optimization
Zhiwei Zhang, Samy Wu Fung, Anastasios Kyrillidis +2
The Boolean satisfiability (SAT) problem lies at the core of many applications in combinatorial optimization, software verification, cryptography, and machine learning. While state…
Verifying Equilibria in Finite-Horizon Probabilistic Concurrent Game Systems
Senthil Rajasekaran, Moshe Y. Vardi
Finite-horizon probabilistic multiagent concurrent game systems, also known as finite multiplayer stochastic games, are a well-studied model in computer science due to their abilit…
Falsification of Autonomous Systems in Rich Environments
Khen Elimelech, Morteza Lahijanian, Lydia E. Kavraki +1
Validating the behavior of autonomous Cyber-Physical Systems (CPS) and Artificial Intelligence (AI) agents, which rely on automated controllers, is an objective of great importance…
Encoding Reusable Multi-Robot Planning Strategies as Abstract Hypergraphs
Khen Elimelech, James Motes, Marco Morales +3
Multi-Robot Task Planning (MR-TP) is the search for a discrete-action plan a team of robots should take to complete a task. The complexity of such problems scales exponentially wit…
Dynamic Programming for Symbolic Boolean Realizability and Synthesis
Yi Lin, Lucas M. Tabajara, Moshe Y. Vardi
Inspired by recent progress in dynamic programming approaches for weighted model counting, we investigate a dynamic-programming approach in the context of boolean realizability and…
Stochastic Games for Interactive Manipulation Domains
Karan Muvvala, Andrew M. Wells, Morteza Lahijanian +2
As robots become more prevalent, the complexity of robot-robot, robot-human, and robot-environment interactions increases. In these interactions, a robot needs to consider not only…
Model Checking Strategies from Synthesis Over Finite Traces
Suguman Bansal, Yong Li, Lucas Martinelli Tabajara +2
The innovations in reactive synthesis from {\em Linear Temporal Logics over finite traces} (LTLf) will be amplified by the ability to verify the correctness of the strategies gener…
Synthesis from Satisficing and Temporal Goals
Suguman Bansal, Lydia Kavraki, Moshe Y. Vardi +1
Reactive synthesis from high-level specifications that combine hard constraints expressed in Linear Temporal Logic LTL with soft constraints expressed by discounted-sum (DS) reward…
DPER: Dynamic Programming for Exist-Random Stochastic SAT
Vu H. N. Phan, Moshe Y. Vardi
In Bayesian inference, the maximum a posteriori (MAP) problem combines the most probable explanation (MPE) and marginalization (MAR) problems. The counterpart in propositional logi…
DPO: Dynamic-Programming Optimization on Hybrid Constraints
Vu H. N. Phan, Moshe Y. Vardi
In Bayesian inference, the most probable explanation (MPE) problem requests a variable instantiation with the highest probability given some evidence. Since a Bayesian network can…
Verification and Realizability in Finite-Horizon Multiagent Systems
Senthil Rajasekaran, Moshe Y. Vardi
The problems of \emph{verification} and \emph{realizability} are two central themes in the analysis of reactive systems. When multiagent systems are considered, these problems have…
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…
Congruence Relations for Büchi Automata
Yong Li, Yih-Kuen Tsay, Andrea Turrini +2
We revisit here congruence relations for Büchi automata, which play a central role in the automata-based verification. The size of the classical congruence relation is in $3^{\math…
Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models
Marcio Nicolau, Anderson R. Tavares, Zhiwei Zhang +4
Computational learning theory states that many classes of boolean formulas are learnable in polynomial time. This paper addresses the understudied subject of how, in practice, such…
On the Power of Automata Minimization in Reactive Synthesis
Shufang Zhu, Lucas M. Tabajara, Geguang Pu +1
Temporal logic is often used to describe temporal properties in AI applications. The most popular language for doing so is Linear Temporal Logic (LTL). Recently, LTL on finite trac…
Reasoning About Strategies: On the Model-Checking Problem
Fabio Mogavero, Aniello Murano, Giuseppe Perelli +1
In open systems verification, to formally check for reliability, one needs an appropriate formalism to model the interaction between agents and express the correctness of the syste…