5 papers
On Solving Simple Curved Nonograms
Maarten Löffler, Günter Rote, Soeren Terziadis +1
Nonograms are a popular type of puzzle, where an arrangement of curves in the plane (in the classic version, a rectangular grid) is given together with a series of hints, indicatin…
Minimum spanning blob-trees
Katharina Klost, Marc van Kreveld, Daniel Perz +2
We investigate blob-trees, a new way of connecting a set of points, by a mixture of enclosing them by cycles (as in the convex hull) and connecting them by edges (as in a spanning…
Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton
Günter Rote
We construct a probabilistic finite automaton (PFA) with 7 states and an input alphabet of 5 symbols for which the PFA Emptiness Problem is undecidable. The only input for the deci…
Probabilistic Finite Automaton Emptiness is undecidable
Günter Rote
It is undecidable whether the language recognized by a probabilistic finite automaton is empty. Several other undecidability results, in particular regarding problems about matrix…
Grid Peeling of Parabolas
Günter Rote, Moritz Rüber, Morteza Saghafian
Grid peeling is the process of repeatedly removing the convex hull vertices of the grid-points that lie inside a given convex curve. It has been conjectured that, for a more and mo…