4 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…