Decidable weighted expressions with Presburger combinators
In this paper, we investigate the expressive power and the algorithmic properties of weighted expressions, which define functions from finite words to integers. First, we consider a slight extension of an expression formalism, ...
The parameterized complexity of the minimum shared edges problem
We study the NP-complete Minimum Shared Edges (MSE) problem, defined as follows. Given an undirected graph, a source and a sink vertex, and two integers p and k, we ask whether there are p paths in the graph connecting the source with ...
Deterministic rendezvous with different maps
We consider a rendezvous problem in which two identical anonymous mobile entities A and B, called later robots, are asked to meet at some node in the network modelled by an arbitrary undirected graph G = ( V , E ). Most of the work ...
Colouring square-free graphs without long induced paths
The complexity of Colouring is fully understood for H-free graphs, but there are still major complexity gaps if two induced subgraphs H 1 and H 2 are forbidden. Let H 1 be the s-vertex cycle C s and H 2 be the t-vertex path P t. We ...
Does adding more agents make a difference? A case study of cover time for the rotor-router
We study the cover time of multiple walks in a graph following the rotor-router mechanism. This mechanism can be seen as a derandomization of multiple random walks, in which agents are propagated by nodes to neighbors in round-robin ...
Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings
In this study, we address the problem of clustering string data in an unsupervised manner by developing a theory of a mixture model and an EM algorithm for strings based on probability theory on a topological monoid of strings ...
Proper learning of k-term DNF formulas from satisfying assignments
In certain applications there may be only positive examples available to learn concepts of a class of interest. Furthermore, learning has to be done properly, i. e. the hypothesis space has to coincide with the concept class, and ...