7 citations · 32 across the 13 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.FL2015
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…
cs.FL2015★ 5 cited
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…
cs.CC2015★ 1 cited
Fractional coverings, greedy coverings, and rectifier networks
Dmitry Chistikov, Szabolcs Iván, Anna Lubiw +1
A rectifier network is a directed acyclic graph with distinguished sources and sinks; it is said to compute a Boolean matrix that has a in the entry iff there is a…