\#P-completeness of counting update digraphs, cacti, and series-parallel decomposition method

DOI10.1007/978-3-030-51466-2_30MaRDI QIDQ2106620zbMATH OpenOpenAlexFDO

Authors Kévin Perrot, Sylvain Sené, Lucas Venturini

Publication date 16 December 2022

Full work available at URL https://arxiv.org/abs/2004.02129

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Combinatorics on update digraphs in Boolean networks
• PSPACE-completeness of majority automata networks
• ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
• Block-sequential update schedules and Boolean automata circuits

Cites work

• A Decomposition for Combinatorial Geometries
• A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
• A logical calculus of the ideas immanent in nervous activity
• Abelian sandpile model and Biggs-Merino polynomial for directed graphs
• Blocs-H-matrices et convergence des méthodes itératives classiques par blocs
• Chip-firing game and a partial Tutte polynomial for Eulerian digraphs
• Combinatorics on update digraphs in Boolean networks
• Graph minors. XX: Wagner's conjecture
• Guided tour of asynchronous cellular automata
• Hard Enumeration Problems in Geometry and Combinatorics
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3266639 (Why is no real title available?)
• Limit cycles and update digraphs in Boolean networks
• Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations
• On the number of different dynamics in Boolean networks with deterministic update schedules
• On the number of update digraphs and its relation with the feedback arc sets and tournaments
• Parallel algorithms for series parallel graphs
• Synchronism versus asynchronism in monotonic Boolean automata networks
• Topology of series-parallel networks
• Tutte polynomials for directed graphs

Cited in

(1)

• Asynchronous, finite dynamical systems

This page was built for publication: \#P-completeness of counting update digraphs, cacti, and series-parallel decomposition method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2106620)