:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Eppstein, David
Format:	Preprint
Published:	2021
Subjects:	Computational Complexity Cellular Automata and Lattice Gases 68Q10, 68Q15, 68Q80 F.1.1
Online Access:	https://arxiv.org/abs/2112.11607
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Cellular automaton model of self-healing
by: Fukś, Henryk, et al.
Published: (2024)

Ternary cellular automata induced by semigroups of order 3 are solvable
by: Fukś, Henryk
Published: (2026)

Fire Spread Modeling using Probabilistic Cellular Automata
by: Ghosh, Rohit, et al.
Published: (2024)

Solving the initial value problem for cellular automata by pattern decomposition
by: Fukś, Henryk
Published: (2025)

On the minimal memory set of cellular automata
by: Castillo-Ramirez, Alonso, et al.
Published: (2024)

One-dimensional cellular automata with a unique active transition
by: Castillo-Ramirez, Alonso, et al.
Published: (2024)

Conway's game Life perturbed
by: Vidunas, Raimundas, et al.
Published: (2025)

Stable finiteness of twisted group rings and noisy linear cellular automata
by: Phung, Xuan Kien
Published: (2022)

Thermodynamic Formalism for a family of cellular automata and duality with the shift
by: Lopes, Artur O., et al.
Published: (2024)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Extended Cellular Automata
by: Mehdipour, Pouya, et al.
Published: (2025)

Weighted Automata and Logics Meet Computational Complexity
by: Kostolányi, Peter
Published: (2023)

Classically Time-Controlled Quantum Automata: Definition and Properties
by: Díaz-Caro, Alejandro, et al.
Published: (2018)

The Serial Scaling Hypothesis
by: Liu, Yuxi, et al.
Published: (2025)

Propositional dynamic logic and asynchronous cascade decompositions for regular trace languages
by: Adsul, Bharat, et al.
Published: (2024)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
by: Böhnlein, Toni, et al.
Published: (2024)

Cellular Automaton Reducibility as a Measure of Complexity for Infinite Words
by: Zubia, Markel, et al.
Published: (2026)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Axiomatizing NFAs Generated by Regular Grammars
by: Gorrieri, Roberto
Published: (2024)

Normal forms in Virus Machines
by: Ramírez-de-Arellano, A., et al.
Published: (2024)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Functional Closure Properties of Finite $\mathbb{N}$-weighted Automata
by: Dörfler, Julian, et al.
Published: (2024)

Positive-rate PCA and IPS with stationary Bernoulli measures are rapidly forgetful
by: Marcovici, Irène, et al.
Published: (2026)

Computing the Bandwidth of Meager Timed Automata
by: Asarin, Eugene, et al.
Published: (2024)

Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

The Algebra of Nondeterministic Finite Automata
by: Gorrieri, Roberto
Published: (2023)

Some derivations among Logarithmic Space Bounded Counting Classes
by: Janaki, V., et al.
Published: (2023)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

Generalized Gottschalk's conjecture for sofic groups and applications
by: Phung, Xuan Kien
Published: (2024)

Weighing Obese Timed Languages
by: Asarin, Eugene, et al.
Published: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Dominant vertices and attractors' landscape for Boolean networks
by: España, Andrea, et al.
Published: (2025)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
by: Filmus, Yuval, et al.
Published: (2020)

Evaluating Massively Parallel Algorithms for DFA Minimisation, Equivalence Checking and Inclusion Checking
by: Heemstra, Jan, et al.
Published: (2025)