| dc.contributor |
Tübingen / Wilhelm-Schickard-Institut für Informatik |
de_DE |
| dc.contributor.author |
Borchert, Bernd |
de_DE |
| dc.date.accessioned |
2003-11-25 |
de_DE |
| dc.date.accessioned |
2014-03-18T10:11:46Z |
|
| dc.date.available |
2003-11-25 |
de_DE |
| dc.date.available |
2014-03-18T10:11:46Z |
|
| dc.date.issued |
2003 |
de_DE |
| dc.identifier.other |
10873191X |
de_DE |
| dc.identifier.uri |
http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-9780 |
de_DE |
| dc.identifier.uri |
http://hdl.handle.net/10900/48518 |
|
| dc.description.abstract |
Giammarresi & Restivo (1992) define locality and recognizability for 2-dimensional
languages. Based on these notions, generalized to the n-dimensional case,
n-dimensionally colorable 1-dimensional languages are introduced.
It is shown: A language L is in NP if and only if L is n-dimensionally colorable for some n.
An analogous characterization in terms of deterministic n-dimensional colorability, based
on a definition of 2-dimensional deterministic recognizability from Reinhardt (1998), is
obtained for P. For an analogous characterization of PSPACE one unbounded dimension
for coloring is added. |
en |
| dc.language.iso |
en |
de_DE |
| dc.publisher |
Universität Tübingen |
de_DE |
| dc.rights |
ubt-nopod |
de_DE |
| dc.rights.uri |
http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=de |
de_DE |
| dc.rights.uri |
http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=en |
en |
| dc.subject.classification |
Komplexitätsklasse NP , Komplexitätstheorie , Formale Sprache |
de_DE |
| dc.subject.ddc |
004 |
de_DE |
| dc.title |
Formal Language Characterizations of P, NP, and PSPACE |
en |
| dc.type |
Report |
de_DE |
| dc.date.updated |
2012-10-11 |
de_DE |
| utue.publikation.fachbereich |
Sonstige - Informations- und Kognitionswissenschaften |
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 |
978 |
de_DE |
| utue.opus.portal |
wsi |
de_DE |
| utue.opus.portalzaehlung |
2003.12000 |
de_DE |
| utue.publikation.source |
WSI ; 2003 ; 12 |
de_DE |
| utue.publikation.reihenname |
WSI-Reports - Schriftenreihe des Wilhelm-Schickard-Instituts für Informatik |
de_DE |
| utue.publikation.zsausgabe |
2003, 12 |
|
| utue.publikation.erstkatid |
2919855-0 |
|
