Deterministically and Sudoku-Deterministically Recognizable Picture Languages

DSpace Repository

Show simple item record

dc.contributor.author Borchert, Bernd de_DE
dc.contributor.author Reinhardt, Klaus de_DE
dc.date.accessioned 2006-10-23 de_DE
dc.date.accessioned 2014-03-18T10:16:05Z
dc.date.available 2006-10-23 de_DE
dc.date.available 2014-03-18T10:16:05Z
dc.date.issued 2006 de_DE
dc.identifier.other 28696015X de_DE
dc.identifier.uri http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-25037 de_DE
dc.identifier.uri http://hdl.handle.net/10900/48966
dc.description.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. en
dc.language.iso en de_DE
dc.publisher Universität Tübingen de_DE
dc.rights ubt-podok de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_mit_pod.php?la=de de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_mit_pod.php?la=en en
dc.subject.classification Bildsprache <Informatik> de_DE
dc.subject.ddc 004 de_DE
dc.subject.other azyklische Graphen de_DE
dc.subject.other acyclic grid graphs en
dc.title Deterministically and Sudoku-Deterministically Recognizable Picture Languages en
dc.type Report (Bericht) de_DE
dc.date.updated 2012-10-11 de_DE
utue.publikation.fachbereich Informatik de_DE
utue.publikation.fakultaet 7 Mathematisch-Naturwissenschaftliche Fakultät de_DE
dcterms.DCMIType Text de_DE
utue.publikation.typ report de_DE
utue.opus.id 2503 de_DE
utue.opus.portal wsi de_DE
utue.opus.portalzaehlung 2006.09000 de_DE
utue.publikation.source WSI ; 2006 ; 9 de_DE
utue.publikation.reihenname WSI-Reports - Schriftenreihe des Wilhelm-Schickard-Instituts für Informatik de_DE
utue.publikation.zsausgabe 2006, 9
utue.publikation.erstkatid 2919855-0

Dateien:

This item appears in the following Collection(s)

Show simple item record