Deterministically and Sudoku-Deterministically Recognizable Picture Languages

DSpace Repository


Dokumentart: Report
Date: 2006
Source: WSI ; 2006 ; 9
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Informatik
DDC Classifikation: 004 - Data processing and computer science
Keywords: Bildsprache <Informatik>
Other Keywords: azyklische Graphen
acyclic grid graphs
Order a printed copy: Print-on-Demand
Show full item record


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.

This item appears in the following Collection(s)