Formal Language Characterizations of P, NP, and PSPACE

DSpace Repositorium (Manakin basiert)

Formal Language Characterizations of P, NP, and PSPACE

Borchert, Bernd
Dateien:
Thumbnail
173. KB
PDF
Zitierfähiger Link (URI): http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-9780
http://hdl.handle.net/10900/48518
Dokumentart: Verschiedenartige Texte
Erscheinungsdatum: 2003
Originalveröffentlichung: WSI ; 2003 ; 12
Sprache: Englisch
Fakultät: 7 Mathematisch-Naturwissenschaftliche Fakultät
Fachbereich: Sonstige - Informations- und Kognitionswissenschaften
DDC-Klassifikation: 004 - Informatik
Schlagworte: Komplexitätsklasse NP , Komplexitätstheorie , Formale Sprache
Lizenz: http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=de http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=en
Zur Langanzeige

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.

Das Dokument erscheint in: