7 citations · 32 across the 13 of their papers we have counts for
9 papers · 1 filter
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…
The Big-O Problem
Dmitry Chistikov, Stefan Kiefer, Andrzej S. Murawski +1
Given two weighted automata, we consider the problem of whether one is big-O of the other, i.e., if the weight of every finite word in the first is not greater than some constant m…
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…
Bisimilarity Distances for Approximate Differential Privacy
Dmitry Chistikov, Andrzej S. Murawski, David Purser
Differential privacy is a widely studied notion of privacy for various models of computation. Technically, it is based on measuring differences between probability distributions. W…
On Restricted Nonnegative Matrix Factorization
Dmitry Chistikov, Stefan Kiefer, Ines Marušić +2
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative matrix into a product of a nonnegative matrix and a nonne…
Complexity of regular abstractions of one-counter languages
Mohamed Faouzi Atig, Dmitry Chistikov, Piotr Hofman +3
We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA)…
Context-Free Commutative Grammars with Integer Counters and Resets
Dmitry Chistikov, Christoph Haase, Simon Halfon
We study the computational complexity of reachability, coverability and inclusion for extensions of context-free commutative grammars with integer counters and reset operations on…
Shortest paths in one-counter systems
Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman +2
We show that any one-counter automaton with states, if its language is non-empty, accepts some word of length at most . This closes the gap between the previously known…
Unary Pushdown Automata and Straight-Line Programs
Dmitry Chistikov, Rupak Majumdar
We consider decision problems for deterministic pushdown automata over a unary alphabet (udpda, for short). Udpda are a simple computation model that accept exactly the unary regul…