Formal Language Characterizations of P, NP, and PSPACE

DSpace Repository


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
Show full item record


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)