Monday January 8th at 4.30pm

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.