Imagen de Portada

Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Junchi, Ma, Weilin, Chen, Chen, Wang, Defu, Lin, Chao, Wang
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Two Graphs: Resolving the Periodic Reversibility of One-dimensional Finite Cellular Automata
por: Wang, Chen, et al.
Publicado: (2024)

Characterization of the set of zero-noise limits measures of perturbed cellular automata
por: Marsan, Hugo, et al.
Publicado: (2024)

Word problems and embedding-obstructions in cellular automata groups on groups
por: Salo, Ville
Publicado: (2025)

Complexity of Boolean automata networks under block-parallel update modes
por: Perrot, Kévin, et al.
Publicado: (2024)

Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata
por: Wang, Chen, et al.
Publicado: (2023)

On the complexity of freezing automata networks of bounded pathwidth
por: Goles, Eric, et al.
Publicado: (2025)

Holomorphic null curves in the special linear group
por: Alarcon, Antonio, et al.
Publicado: (2025)

The PCP-like Theorem for Sub-linear Time Inapproximability
por: Ma, Hengzhao, et al.
Publicado: (2021)

Efficient algorithms for collecting the statistics of large-scale IP address data
por: Liu, Hui, et al.
Publicado: (2021)

Entropy of pebble automata and space complexity
por: Montoya, J. Andres
Publicado: (2026)

A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system
por: Ivanov, Sergiu, et al.
Publicado: (2024)

Complete ergodicity in one-dimensional reversible cellular automata
por: Shiraishi, Naoto, et al.
Publicado: (2024)

Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem
por: Garg, Abhibhav, et al.
Publicado: (2025)

Solving convex QPs with structured sparsity under indicator conditions
por: Bienstock, Daniel, et al.
Publicado: (2024)

Encoding of algebraic geometry codes with quasi-linear complexity $O(N\log N)$
por: Li, Songsong, et al.
Publicado: (2024)

Learning complexity of gradient descent and conjugate gradient algorithms
por: Jiao, Xianqi, et al.
Publicado: (2024)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
por: Ostonov, Azimkhon, et al.
Publicado: (2023)

A proof of P != NP (New symmetric encryption algorithm against any linear attacks and differential attacks)
por: Ming, Gao
Publicado: (2022)

Rice-like complexity lower bounds for Boolean and uniform automata networks
por: Goubault-Larrecq, Aliénor, et al.
Publicado: (2024)

Hazard-free Decision Trees
por: Benson, Deepu, et al.
Publicado: (2025)

Classical and quantum Merlin-Arthur automata
por: Yakaryılmaz, Abuzer
Publicado: (2022)

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
por: Gupta, Rishav, et al.
Publicado: (2026)

On complexity of restricted fragments of Decision DNNF
por: Calí, Andrea, et al.
Publicado: (2025)

From FPT Decision to FPT Enumeration
por: Creignou, Nadia, et al.
Publicado: (2025)

When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?
por: Chen, Yuansi, et al.
Publicado: (2023)

An alternative explicit circuit diagram for the quantum search algorithm by implementing a non-unitary gate
por: Daskin, Ammar
Publicado: (2024)

Embedding arbitrary Boolean circuits into fungal automata with arbitrary update sequences
por: Goles, Eric, et al.
Publicado: (2026)

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
por: Li, Shuangle, et al.
Publicado: (2024)

Exact spectral gaps of random one-dimensional quantum circuits
por: Deneris, Andrew E., et al.
Publicado: (2024)

Explaining the Ubiquity of Phase Transitions in Decision Problems
por: Jackson, Andrew
Publicado: (2025)

Injective hardness condition for PCSPs
por: Banakh, Demian, et al.
Publicado: (2024)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
por: Fortnow, Lance
Publicado: (2025)

On one-way functions and the average time complexity of almost-optimal compression
por: Zimand, Marius
Publicado: (2024)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
por: Bender, Matías, et al.
Publicado: (2025)

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
por: Jackson, Andrew
Publicado: (2025)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
por: Alhamdan, Yousef M.
Publicado: (2025)

Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes
por: Yang, Chao, et al.
Publicado: (2024)

Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
por: Yang, Chao, et al.
Publicado: (2024)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
por: Colli, Giordano
Publicado: (2025)