17 citations · 18 across the 2 of their papers we have counts for
4 papers
Simplest Non-Regular Deterministic Context-Free Language
Petr Jancar, Jiri Sima
We introduce a new notion of C-simple problems for a class C of decision problems (i.e. languages), w.r.t. a particular reduction. A problem is C-simple if it can be reduced to eac…
Stronger Separation of Analog Neuron Hierarchy by Deterministic Context-Free Languages
Jiří Šíma
We analyze the computational power of discrete-time recurrent neural networks (NNs) with the saturated-linear activation function within the Chomsky hierarchy. This model restricte…
A polynomial-time construction of a hitting set for read-once branching programs of width 3
Jiří Šíma, Stanislav Žák
Recently, an interest in constructing pseudorandom or hitting set generators for restricted branching programs has increased, which is motivated by the fundamental issue of derando…
On the NP-Completeness of Some Graph Cluster Measures
Jiri Sima, Satu Elisa Schaeffer
Graph clustering is the problem of identifying sparsely connected dense subgraphs (clusters) in a given graph. Proposed clustering algorithms usually optimize various fitness funct…