About: Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	We resume computational complexity aspects of several models of membrane systems, namely P systems with active membranes, P systems with proteins on membranes and tissue P systems both with membrane separation and membrane division. A sequence of common issues is studied in relation to these P system models, and 16 open problems are stated in the text. We question the role of families of P systems and their necessity to solve computationally hard problems in polynomial time. For each P system model we focus on conditions guaranteeing the polynomial equivalence of families of P systems and Turing machines. The ability of P systems to solve NP/co-NP-complete problems in polynomial time (trading space for time) is a very popular issue. Interesting characterizations of the borderline between tractability and intractability, i.e., P/NP, have been recently shown. Similarly important, although less popular, is the relation between NP/co-NP and further classes as PP, the polynomial hierarchy PH and PSPACE. Several models of P systems has been shown to characterize the class PSPACE which itself characterizes parallel computations with an unlimited number of processors but a limited propagation of data between them. We resume computational complexity aspects of several models of membrane systems, namely P systems with active membranes, P systems with proteins on membranes and tissue P systems both with membrane separation and membrane division. A sequence of common issues is studied in relation to these P system models, and 16 open problems are stated in the text. We question the role of families of P systems and their necessity to solve computationally hard problems in polynomial time. For each P system model we focus on conditions guaranteeing the polynomial equivalence of families of P systems and Turing machines. The ability of P systems to solve NP/co-NP-complete problems in polynomial time (trading space for time) is a very popular issue. Interesting characterizations of the borderline between tractability and intractability, i.e., P/NP, have been recently shown. Similarly important, although less popular, is the relation between NP/co-NP and further classes as PP, the polynomial hierarchy PH and PSPACE. Several models of P systems has been shown to characterize the class PSPACE which itself characterizes parallel computations with an unlimited number of processors but a limited propagation of data between them. (en)
Title	Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges (en)
skos:prefLabel	Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges (en)
skos:notation	RIV/47813059:19240/14:#0005320!RIV15-MSM-19240___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(ED1.1.00/02.0070)
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Sosík, Petr
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Slezská univerzita v Opavě / Filozoficko-přírodovědecká fakulta
http://linked.open...dnocenehoVysledku	1524
http://linked.open...ai/riv/idVysledku	RIV/47813059:19240/14:#0005320
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Membrane computing; active membrane; tissue P system; complexity (en)
http://linked.open.../riv/klicoveSlovo	complexity Membrane computing active membrane tissue P system
http://linked.open...ontrolniKodProRIV	[86629C087332]
http://linked.open...v/mistoKonaniAkce	Moldavská republika
http://linked.open...i/riv/mistoVydani	Berlin
http://linked.open...i/riv/nazevZdroje	Membrane Computing - 14th International Conference
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	1 (xsd:int)
http://linked.open...vavai/riv/projekt	IT4Innovations Centre of Excellence
http://linked.open...UplatneniVysledku	2014
http://linked.open...iv/tvurceVysledku	Sosík, Petr
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2013-01-01 (xsd:date)
issn	0302-9743
number of pages	15 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Springer-Verlag
https://schema.org/isbn	978-3-642-54238-1
http://localhost/t...ganizacniJednotka	19240

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 75 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software