Cover Image

Word problems and embedding-obstructions in cellular automata groups on groups

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Salo, Ville
Format:	Preprint
Published:	2025
Subjects:	Group Theory Computational Complexity Formal Languages and Automata Theory Dynamical Systems
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Graph and wreath products of cellular automata
by: Salo, Ville
Published: (2020)

On the order of lazy cellular automata
by: Alcalá-Arroyo, Edgar, et al.
Published: (2025)

Topological transitivity of group cellular automata is decidable
by: Castronuovo, Niccolò, et al.
Published: (2026)

Membership and Conjugacy in Inverse Semigroups
by: Fleischer, Lukas, et al.
Published: (2025)

Idempotent cellular automata and their natural order
by: Castillo-Ramirez, Alonso, et al.
Published: (2024)

A categorical framework for cellular automata
by: Castillo-Ramirez, A., et al.
Published: (2026)

Cellular automata can really solve the parity problem
by: Wolnik, Barbara, et al.
Published: (2025)

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

Connections between the minimal neighborhood and the activity value of cellular automata
by: Castillo-Ramirez, Alonso, et al.
Published: (2025)

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

Equality of cycle lengths in one- and two-dimensional $σ$ automata
by: Vadali, Avi, et al.
Published: (2025)

On linguistic subsets of groups and monoids
by: Carvalho, André, et al.
Published: (2025)

Computational Dynamical Systems
by: Cotler, Jordan, et al.
Published: (2024)

Membership problems in nilpotent groups
by: Bodart, Corentin
Published: (2024)

Geodesic languages for rational subsets and conjugates in virtually free groups
by: Carvalho, André, et al.
Published: (2024)

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

Decidable problems in substitution shifts
by: Béal, Marie-Pierre, et al.
Published: (2021)

A language-theoretic approach to study the density of subsets in free groups
by: Carvalho, André
Published: (2026)

Distortion element in the automorphism group of a full shift
by: Callard, Antonin, et al.
Published: (2022)

Multiband linear cellular automata and endomorphisms of algebraic vector groups
by: Byszewski, Jakub, et al.
Published: (2022)

Submonoid Membership in n-dimensional lamplighter groups and S-unit equations
by: Dong, Ruiwen
Published: (2024)

On finite extensions of lamplighter groups
by: Bodart, Corentin
Published: (2025)

Further results on generalized cellular automata
by: Castillo-Ramirez, Alonso, et al.
Published: (2023)

Finding codes on infinite grids automatically
by: Salo, Ville, et al.
Published: (2023)

Word equations, constraints, and formal languages
by: Ciobanu, Laura
Published: (2024)

Proceedings of the 15th International Workshop on Non-Classical Models of Automata and Applications
by: Moreira, Nelma, et al.
Published: (2025)

On the complexity of computing Strahler numbers
by: Ganardi, Moses, et al.
Published: (2025)

Studying homing and synchronizing sequences for Timed Finite State Machines with output delays
by: Vinarskii, Evgenii, et al.
Published: (2025)

Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems
by: Chen, Zeyu, et al.
Published: (2025)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
by: Podolskii, Vladimir, et al.
Published: (2024)

Regular Expressions with Backreferences and Lookaheads Capture NLOG
by: Uezato, Yuya
Published: (2024)

Maximal Length Cellular Automata : A Survey
by: Adak, Sumit, et al.
Published: (2024)

Trading Determinism for Noncommutativity in Edmonds' Problem
by: Arvind, V., et al.
Published: (2024)

Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
by: Gezer, M. Utkan, et al.
Published: (2020)

Visibly Recursive Automata
by: Dubrulle, Kévin, et al.
Published: (2026)

Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
by: Yamakami, Tomoyuki
Published: (2022)

Review of Automaton Learning Algorithms with Polynomial Complexity -- Completely Solved Examples
by: Haneef, Farah
Published: (2024)

Complexity of Unary Exclusive Nondeterministic Finite Automata
by: Kutrib, Martin, et al.
Published: (2024)

Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
by: Yamakami, Tomoyuki
Published: (2023)