We provide a uniform solution to the problem of synthesizing finite-state distributed system. An instance synthesis consists system architecture and temporal specification. The is given as directed graph, where nodes represent processes (including environment special process) that communicate synchronously through shared variables attached edges. same variable may occur on multiple outgoing edges single node, allowing for broadcast data. A collection programs in architecture, such joint...

Adversarial training has been shown to be one of the most effective approaches improve robustness deep neural networks. It is formalized as a min-max optimization over model weights and adversarial perturbations, where can optimized through gradient descent methods like SGD. In this paper, we show that treating random variables allows for enhancing Second-Order Statistics Optimization (S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> O)...

The precise complexity of complementing B\uchi automata is an intriguing and long standing problem. While optimal complementation techniques for finite are simple -- it suffices to determinize them using a subset construction dualize the acceptance condition resulting automaton more involved. Indeed, EXPTIME procedure took quarter century from introduction in early $60$s, stepwise narrowing gap between upper lower bound exponent (of $(6e)^n$ with $n$ states) four decades. distance known...

Parity games play an important role in model checking and synthesis. In their paper, Calude et al. have recently shown that these can be solved quasi-polynomial time. We show algorithm implemented efficiently: we use data structure as a progress measure, allowing for backward implementation instead of complete unravelling the game. To achieve this, number changes to made techniques, where main one is add power antagonistic player allows determining her rational move without changing outcome...

Model checking is a well-established technique for the formal verification of concurrent and distributed systems. In recent years, model has been extended adapted multi-agent systems, primarily to enable analysis belief–desire–intention While this successful, there need more complex logical frameworks in order verify realistic particular, probabilistic real-time aspects, as well knowledge, belief, goals, etc., are required. However, development new tools combinations logics both difficult...

The bottleneck in the quantitative analysis of Markov chains and decision processes against specifications given LTL or as some form nondeterministic Buchi automata is inclusion a determinisation step automaton under consideration. In this paper, we show that full can be avoided: subset breakpoint constructions suffice. We have implemented our approach - both explicit symbolic versions prototype tool. Our experiments compete with mature tools like PRISM.

In this paper we study the problem of minimising deterministic automata over finite and infinite words. Deterministic are simplest devices to recognise regular languages, \buchi, \cobuchi, parity play a similar role in recognition $\omega$-regular languages. While it is well known that minimisation weak cheap, complexity \buchi has remained an open challenge. We establish NP-completeness these problems. A second contribution introduction almost equivalence, equivalence class for strictly...

The precise complexity of complementing Büchi automata is an intriguing and long standing problem. While optimal complementation techniques for finite are simple - it suffices to determinize them using a subset construction dualize the acceptance condition resulting automaton more involved. Indeed, EXPTIME procedure took quarter century from introduction in early 60s, stepwise narrowing gap between upper lower bound exponent (of (6e)n with n states) four decades. distance known (O'(0.96...