Discrete Mathematics and Optimization Seminar

University of Tuebingen
Monday January 8th at 4.30pm
Burnside 1205

Title. Deterministically and Sudoku-deterministically recognizable picture languages.

Abstract. The recognizable 2-dimensional languages are a robust class with many characterizations, comparable to the
regular languages in the 1-dimensional case. One characterization is by tiling systems. The corresponding
word problem is NP-complete. Therefore, notions of determinism for tiling systems were suggested. For the
notion which was called "deterministically recognizable" it was open since 1998 whether it implies
recognizability. By showing that acyclicity of grid graphs is recognizable we answer this
question positively. In contrast to that, we show that non-recognizable languages can be accepted by a
generalization of this tiling system determinism which we call Sudoku-determinism. Its word problem,
however, is still in linear time. We show that Sudoku-determinism even contains the set of
2-dimensional languages which can be recognized by 4-way alternating automata.