Type of Publication:  Contribution to a conference 
Author:  Kosub, Sven; Homan, Christopher M. 
Year of publication:  2007 
Conference:  ICTCS, Oct 3, 2007  Oct 5, 2007, Rome, Italy 
Published in:  Proceedings of the 10th Italian Conference on Theoretical Computer Science / Italiano, Giuseppe F. et al. (ed.).  Singapore [u.a.] : World Scientific, 2007.  pp. 163174 
Summary: 
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 minfunctions, all maxfunctions, or all selfdual and monotone functions, and G contains all planar graphs, then it is #Pcomplete 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.

Subject (DDC):  004 Computer Science 
Files  Size  Format  View 

There are no files associated with this item. 
KOSUB, Sven, Christopher M. HOMAN, 2007. Dichotomy Results for Fixed Point Counting in Boolean Dynamical Systems. ICTCS. Rome, Italy, Oct 3, 2007  Oct 5, 2007. In: ITALIANO, Giuseppe F., ed. and others. Proceedings of the 10th Italian Conference on Theoretical Computer Science. Singapore [u.a.]:World Scientific, pp. 163174
@inproceedings{Kosub2007Dicho3057, title={Dichotomy Results for Fixed Point Counting in Boolean Dynamical Systems}, year={2007}, address={Singapore [u.a.]}, publisher={World Scientific}, booktitle={Proceedings of the 10th Italian Conference on Theoretical Computer Science}, pages={163174}, editor={Italiano, Giuseppe F.}, author={Kosub, Sven and Homan, Christopher M.} }
<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/22rdfsyntaxns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digitalrepositories.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.unikonstanz.de/rdf/resource/123456789/3057"> <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 minfunctions, all maxfunctions, or all selfdual and monotone functions, and G contains all planar graphs, then it is #Pcomplete 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:language>eng</dc:language> <dcterms:bibliographicCitation>Publ. in: Proceedings of the 10th Italian Conference on Theoretical Computer Science, ICTCS'07 : Rome, Italy, 3  5 October 2007 / Eds.: Giuseppe F. Italiano ...  Singapore [u.a.] : World Scientific, 2007, pp. 163174</dcterms:bibliographicCitation> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:creator>Kosub, Sven</dc:creator> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dspace:isPartOfCollection rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/36"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20110323T10:15:58Z</dcterms:available> <dc:contributor>Kosub, Sven</dc:contributor> <dcterms:issued>2007</dcterms:issued> <dcterms:isPartOf rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/36"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20110323T10:15:58Z</dc:date> <dc:rights>termsofuse</dc:rights> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dc:contributor>Homan, Christopher M.</dc:contributor> <bibo:uri rdf:resource="http://kops.unikonstanz.de/handle/123456789/3057"/> <dcterms:title>Dichotomy Results for Fixed Point Counting in Boolean Dynamical Systems</dcterms:title> <dc:creator>Homan, Christopher M.</dc:creator> </rdf:Description> </rdf:RDF>