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.