Zugang zum Dokument
Borchert, Bernd ; Reinhardt, Klaus:
Deterministically and Sudoku-Deterministically Recognizable Picture Languages
|
 PDF 197kB
|
| Zitierfähiger Link: | Bitte nutzen Sie diese URL, um auf das Dokument zu verlinken oder es zu zitieren: http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-25037 |
|---|---|
| URL: | http://tobias-lib.uni-tuebingen.de/volltexte/2006/2503/ |
| Originalveröffentlichung: | WSI ; 2006-09 |
| Fachgebiet/Einrichtung: | 17 Wilhelm-Schickard-Institut für Informatik |
| Dokumentart: | Report (Bericht) |
| Sprache: | Englisch |
| Erstellungsjahr: | 2006 |
| Publikationsdatum: | 23.10.2006 |
| Kurze Inhaltszusammenfassung auf Englisch | 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. |
| Kontrollierte Schlagwörter (Deutsch): | Bildsprache <Informatik> |
| Freie Schlagwörter (Deutsch): | azyklische Graphen |
| Freie Schlagwörter (Englisch): | acyclic grid graphs |
| DDC-Sachgruppe: | Informatik |
| Gedruckte Kopie bestellen: |
Print-on-Demand
|
| Lizenz: |
Veröffentlichungsvertrag mit Print-on-Demand
|
