Formal Language Characterizations of P, NP, and PSPACE

DSpace Repository

Formal Language Characterizations of P, NP, and PSPACE

Borchert, Bernd
Dateien:
Thumbnail
173. KB
PDF
URI: http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-9780
http://hdl.handle.net/10900/48518
Dokumentart: Report
Date: 2003
Source: WSI ; 2003 ; 12
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Sonstige - Informations- und Kognitionswissenschaften
DDC Classifikation: 004 - Data processing and computer science
Keywords: Komplexitätsklasse NP , Komplexitätstheorie , Formale Sprache
License: 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
Show full item record

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.

This item appears in the following Collection(s)