KOPS - Das Institutionelle Repositorium der Universität Konstanz

Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems

Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

KOSUB, Sven, 2008. Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems. In: Mathematics in Computer Science. 1(3), pp. 487-505

@article{Kosub2008Dicho-3017, title={Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems}, year={2008}, doi={10.1007/s11786-007-0038-y}, number={3}, volume={1}, journal={Mathematics in Computer Science}, pages={487--505}, author={Kosub, Sven} }

<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/3017"> <dc:creator>Kosub, Sven</dc:creator> <dcterms:issued>2008</dcterms:issued> <dcterms:abstract xml:lang="eng">A complete classification of the computational complexity of the fixed-point existence problem for Boolean dynamical systems, i.e., finite discrete dynamical systems over the domain {0, 1}, is presented. For function classes F and graph classes G, an (F, G)-system is a Boolean dynamical system such that all local transition functions lie in F and the underlying graph lies in G. Let F be a class of Boolean functions which is closed under composition and let G be a class of graphs which is closed under taking minors. The following dichotomy theorems are shown: (1) If F contains the self-dual functions and G contains the planar graphs, then the fixed-point existence problem for (F, G)-systems with local transition function given by truth-tables is NPcomplete; otherwise, it is decidable in polynomial time. (2) If F contains the self-dual functions and G contains the graphs having vertex covers of size one, then the fixed-point existence problem for (F, G)-systems with local transition function given by formulas or circuits is NP-complete; otherwise, it is decidable in polynomial time.</dcterms:abstract> <dc:contributor>Kosub, Sven</dc:contributor> <dcterms:rights rdf:resource="http://nbn-resolving.org/urn:nbn:de:bsz:352-20140905103416863-3868037-7"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-23T10:15:47Z</dc:date> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-23T10:15:47Z</dcterms:available> <dcterms:title>Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems</dcterms:title> <dcterms:bibliographicCitation>Publ. in: Mathematics in Computer Science, 1 (2008), 3, pp. 487-505</dcterms:bibliographicCitation> <dc:language>eng</dc:language> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/3017"/> <dc:rights>deposit-license</dc:rights> </rdf:Description> </rdf:RDF>

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto