KOPS - The Institutional Repository of the University of Konstanz

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

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

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

KOSUB, Sven, 2008. Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems. In: Mathematics in Computer Science. 1(3), pp. 487-505. Available under: doi: 10.1007/s11786-007-0038-y

@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:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" 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> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:issued>2008</dcterms:issued> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <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> <dc:rights>terms-of-use</dc:rights> <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:rights rdf:resource="https://kops.uni-konstanz.de/page/termsofuse"/> <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> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/3017"/> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account