Buchumschlag

Rice-like complexity lower bounds for Boolean and uniform automata networks

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Goubault-Larrecq, Aliénor, Perrot, Kévin
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Discrete Mathematics Computational Complexity Logic in Computer Science
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
von: Geniet, Colin, et al.
Veröffentlicht: (2026)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
von: Goubault-Larrecq, Aliénor, et al.
Veröffentlicht: (2025)

Complexity of Boolean automata networks under block-parallel update modes
von: Perrot, Kévin, et al.
Veröffentlicht: (2024)

Hardness of monadic second-order formulae over succinct graphs
von: Gamard, Guilhem, et al.
Veröffentlicht: (2023)

The Unit Gap: How Sharing Works in Boolean Circuits
von: Krinkin, Kirill
Veröffentlicht: (2026)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
von: Zhang, Tianwei, et al.
Veröffentlicht: (2024)

On the complexity of freezing automata networks of bounded pathwidth
von: Goles, Eric, et al.
Veröffentlicht: (2025)

The Rise of Plurimorphisms: Algebraic Approach to Approximation
von: Barto, Libor, et al.
Veröffentlicht: (2024)

On the number of asynchronous attractors in AND-NOT Boolean networks
von: Trinh, Van-Giang, et al.
Veröffentlicht: (2025)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
von: Seppelt, Tim
Veröffentlicht: (2024)

Restricted CSPs and F-free Digraph Algorithmics
von: Guzmán-Pro, Santiago, et al.
Veröffentlicht: (2025)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
von: Seppelt, Tim
Veröffentlicht: (2023)

The Richness of CSP Non-redundancy
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

A Classification of Long-Refinement Graphs for Colour Refinement
von: Kiefer, Sandra, et al.
Veröffentlicht: (2025)

CMSO-transducing tree-like graph decompositions
von: Campbell, Rutger, et al.
Veröffentlicht: (2024)

Computability of extender sets in multidimensional subshifts: asymptotic growths, dynamical constraints
von: Callard, Antonin, et al.
Veröffentlicht: (2024)

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
von: Dwivedi, Prateek, et al.
Veröffentlicht: (2026)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
von: Černý, Marek, et al.
Veröffentlicht: (2025)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
von: Černý, Marek
Veröffentlicht: (2026)

Smaller Circuits for Bit Addition
von: Goncharov, Mikhail, et al.
Veröffentlicht: (2025)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
von: Roberson, David E., et al.
Veröffentlicht: (2023)

Continuous Petri Nets Faithfully Fluidify Most Permissive Boolean Networks
von: Haar, Stefan, et al.
Veröffentlicht: (2025)

Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
von: Concha-Vega, Pablo, et al.
Veröffentlicht: (2025)

Graph Homomorphisms and Universal Algebra
von: Bodirsky, Manuel
Veröffentlicht: (2026)

Weighted basic parallel processes and combinatorial enumeration
von: Clemente, Lorenzo
Veröffentlicht: (2024)

Boolean proportions
von: Antić, Christian
Veröffentlicht: (2021)

FO logic on cellular automata orbits equals MSO logic
von: Theyssier, Guillaume
Veröffentlicht: (2024)

Creation of fixed points in block-parallel Boolean automata networks
von: Perrot, Kévin, et al.
Veröffentlicht: (2025)

Verifying Sampling Algorithms via Distributional Invariants
von: Zilken, Daniel, et al.
Veröffentlicht: (2025)

First order complexity of finite random structures
von: Demin, Danila, et al.
Veröffentlicht: (2024)

Boolean Variation and Boolean Logic BackPropagation
von: Nguyen, Van Minh
Veröffentlicht: (2023)

Symmetric Arithmetic Circuits
von: Dawar, Anuj, et al.
Veröffentlicht: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
von: Dawar, Anuj, et al.
Veröffentlicht: (2021)

Logic-based analogical proportions
von: Antić, Christian
Veröffentlicht: (2024)

A Note on Constructive Canonical Splitter Strategies in Nowhere Dense Graph Classes
von: Fuchser, Janne, et al.
Veröffentlicht: (2025)

Nested Sequents for Intuitionistic Grammar Logics via Structural Refinement
von: Lyon, Tim S.
Veröffentlicht: (2022)

VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
von: Chang, Fan, et al.
Veröffentlicht: (2025)

Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
von: Adler, Isolde, et al.
Veröffentlicht: (2025)

Relations between monotone complexity measures based on decision tree complexity
von: Byramji, Farzan, et al.
Veröffentlicht: (2024)

On the consistency of stronger lower bounds for NEXP
von: Thapen, Neil
Veröffentlicht: (2025)