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…
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…
The Generalized Combinatorial Lason-Alon-Zippel-Schwartz Nullstellensatz Lemma
Günter Rote
We survey a few strengthenings and generalizations of the Combinatorial Nullstellensatz of Alon and the Schwartz-Zippel Lemma. These lemmas guarantee the existence of (a certain nu…