
Presburger arithmetic with threshold counting quantifiers is easy
We give a quantifier elimination procedures for the extension of Presbur...
read it

Subcubic Certificates for CFL Reachability
Many problems in interprocedural program analysis can be modeled as the ...
read it

The BigO Problem for Labelled Markov Chains and Weighted Automata
Given two weighted automata, we consider the problem of whether one is b...
read it

Globehopping
We consider versions of the grasshopper problem (Goulko and Kent, 2017) ...
read it

Convergence of Opinion Diffusion is PSPACEcomplete
We analyse opinion diffusion in social networks, where a finite set of i...
read it

Repairing brackets
Consider the following oneplayer game. Take a wellformed sequence of o...
read it

Bisimilarity Distances for Approximate Differential Privacy
Differential privacy is a widely studied notion of privacy for various m...
read it

OMinimal Invariants for Linear Loops
The termination analysis of linear loops plays a key role in several are...
read it

Approximate Counting in SMT and Value Estimation for Probabilistic Programs
#SMT, or model counting for logical theories, is a wellknown hard probl...
read it
Dmitry Chistikov
is this you? claim profile