### Compositional Algorithms for Succinct Safety Games

**2016-02-03**

1602.01174 | cs.LO

We study the synthesis of circuits for succinct safety specifications given
in the AIG format. We show how AIG safety specifications can be decomposed
automatically into sub specifications. Then we propose symbolic compositional
algorithms to solve the synthesis problem compositionally starting for the
sub-specifications. We have evaluated the compositional algorithms on a set of
benchmarks including those proposed for the first synthesis competition
organised in 2014 by the Synthesis Workshop affiliated to the CAV conference.
We show that a large number of benchmarks can be decomposed automatically and
solved more efficiently with the compositional algorithms that we propose in
this paper.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2018-01-07**

1801.02124 | stat.ML

This paper considers the problem of inverse reinforcement learning in
zero-sum stochastic games when… show more

**2019-01-11**

1901.03619 | cs.SY

We describe an approximate dynamic programming approach to compute lower
bounds on the optimal value… show more

**2015-09-18**

1509.05664 | cs.SE

In this paper, we introduce an SMT-based method that automatically
synthesizes a distributed self-st… show more

**2018-03-05**

1803.02884 | cs.AI

This paper considers parametric Markov decision processes (pMDPs) whose
transitions are equipped wit… show more

**2018-11-15**

1811.06503 | cs.GT

Computing Nash equilibria for strategic multi-agent systems is challenging
for expensive black box s… show more

**2016-12-23**

1612.08070 | quant-ph

Understanding quantum speed-up over classical computing is fundamental for
the development of effici… show more

**2018-01-16**

1801.05079 | cs.CC

The one way function based on the Collatz problem is proposed. It is based on
the problem's conditio… show more

**2018-07-24**

1807.08970 | quant-ph

Suppose we have a small quantum computer with only M qubits. Can such a
device genuinely speed up ce… show more

**2017-05-23**

1705.08426 | cs.LO

LTLf synthesis is the process of finding a strategy that satisfies a linear
temporal specification o… show more

**2013-04-21**

1304.5719 | cs.DC

Consider a complete communication network on $n$ nodes, each of which is a
state machine. In synchro… show more

**2019-06-12**

1906.05224 | cs.GT

The idea of approximating the Shapley value of an n-person game by random
sampling was introduced by… show more

**2017-10-26**

1710.09595 | cs.CC

In this paper, we consider online algorithms. Typically the model is
investigated with respect to co… show more

**2012-07-03**

1207.0560 | cs.DS

We extend the work of Narasimhan and Bilmes [30] for minimizing set functions
representable as a dif… show more

**2013-11-06**

1311.1338 | cs.DS

The experimental analysis of meta-heuristic algorithm performance is usually
based on comparing aver… show more

**2019-03-29**

1903.12576 | cs.LO

The synthesis - the automatic construction - of reactive systems from linear
temporal logic (LTL) sp… show more

**2016-07-01**

1607.00372 | cs.PF

We consider the fixed-delay synthesis problem for continuous-time Markov
chains extended with fixed-… show more