1 citations · 1 across the 1 of their papers we have counts for
10 papers
Presburger arithmetic with threshold counting quantifiers is easy
Dmitry Chistikov, Christoph Haase, Alessio Mansutti
We give a quantifier elimination procedures for the extension of Presburger arithmetic with a unary threshold counting quantifier that determines whether the nu…
Subcubic Certificates for CFL Reachability
Dmitry Chistikov, Rupak Majumdar, Philipp Schepper
Many problems in interprocedural program analysis can be modeled as the context-free language (CFL) reachability problem on graphs and can be solved in cubic time. Despite years of…
Rational subsets of Baumslag-Solitar groups
Michaël Cadilhac, Dmitry Chistikov, Georg Zetzsche
We consider the rational subset membership problem for Baumslag-Solitar groups. These groups form a prominent class in the area of algorithmic group theory, and they were recently…
Globe-hopping
Dmitry Chistikov, Olga Goulko, Adrian Kent +1
We consider versions of the grasshopper problem (Goulko and Kent, 2017) on the circle and the sphere, which are relevant to Bell inequalities. For a circle of circumference , w…
Convergence of Opinion Diffusion is PSPACE-complete
Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson +1
We analyse opinion diffusion in social networks, where a finite set of individuals is connected in a directed graph and each simultaneously changes their opinion to that of the maj…
Re-pairing brackets
Dmitry Chistikov, Mikhail Vyalyi
Consider the following one-player game. Take a well-formed sequence of opening and closing brackets. As a move, the player can pair any opening bracket with any closing bracket to…