Dichotomy results for fixed point counting in boolean dynamical systems

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

HOMAN, Christopher M., Sven KOSUB, 2015. Dichotomy results for fixed point counting in boolean dynamical systems. In: Theoretical Computer Science. 573, pp. 16-25. ISSN 0304-3975. eISSN 1879-2294

@article{Homan2015Dicho-30961, title={Dichotomy results for fixed point counting in boolean dynamical systems}, year={2015}, doi={10.1016/j.tcs.2015.01.040}, volume={573}, issn={0304-3975}, journal={Theoretical Computer Science}, pages={16--25}, author={Homan, Christopher M. and 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/30961"> <dc:creator>Kosub, Sven</dc:creator> <dc:creator>Homan, Christopher M.</dc:creator> <dcterms:title>Dichotomy results for fixed point counting in boolean dynamical systems</dcterms:title> <dcterms:abstract xml:lang="eng">We present dichotomy theorems regarding the computational complexity of counting fixed points in boolean (discrete) dynamical systems, i.e., finite discrete dynamical systems over the domain {0,1}. For a class F of boolean functions and a class G of graphs, an (F,G)-system is a boolean dynamical system with local transitions functions lying in F and graphs in G. We show that, if local transition functions are given by lookup tables, then the following complexity classification holds: Let F be a class of boolean functions closed under superposition and let G be a graph class closed under taking minors. If F contains all min-functions, all max-functions, or all self-dual and monotone functions, and GG contains all planar graphs, then it is #P-complete to compute the number of fixed points in an (F,G)-system; otherwise it is computable in polynomial time. We also prove a dichotomy theorem for the case that local transition functions are given by formulas (over logical bases). This theorem has a significantly more complicated structure than the theorem for lookup tables. A corresponding theorem for boolean circuits coincides with the theorem for formulas.</dcterms:abstract> <dc:contributor>Homan, Christopher M.</dc:contributor> <dcterms:issued>2015</dcterms:issued> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/30961"/> <dc:contributor>Kosub, Sven</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2015-05-18T09:04:32Z</dc:date> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2015-05-18T09:04:32Z</dcterms:available> <dc:language>eng</dc:language> </rdf:Description> </rdf:RDF>

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto