Cover Image

Cellular Automaton Reducibility as a Measure of Complexity for Infinite Words

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zubia, Markel, Geuvers, Herman
Format:	Preprint
Published:	2026
Subjects:	Formal Languages and Automata Theory 68Q80 (Primary) 06A06, 68R15 (Secondary) F.1.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Languages of Words of Low Automatic Complexity Are Hard to Compute
by: Chen, Joey, et al.
Published: (2025)

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

The decidability of the genus of regular languages and directed emulators
by: Bonfante, Guillaume, et al.
Published: (2021)

Deterministic Suffix-reading Automata
by: Keerthan, R, et al.
Published: (2025)

List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata
by: Volkov, Mikhail V.
Published: (2025)

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

A cornering strategy for synchronizing a DFA
by: Bradshaw, Peter, et al.
Published: (2024)

The Complexity of Iterated Reversible Computation
by: Eppstein, David
Published: (2021)

On Transition Constructions for Automata -- A Categorical Perspective
by: Cruchten, Mike
Published: (2024)

Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata
by: Guillon, Bruno, et al.
Published: (2025)

Kleene Theorems for Lasso Languages and $ω$-Languages
by: Cruchten, Mike
Published: (2024)

Input-Erasing Two-Way Finite Automata
by: Meduna, Alexander, et al.
Published: (2025)

A Note on the Relation between Recognisable Series and Regular Sequences, and their Minimal Linear Representations
by: Heuberger, Clemens, et al.
Published: (2022)

Templated Assembly Theory: An Extension of the Canonical Assembly Index with Block-Compressed Template
by: Masierak, Piotr
Published: (2026)

The generating power of weighted tree automata with initial algebra semantics
by: Droste, Manfred, et al.
Published: (2024)

Density of rational languages under shift invariant measures
by: Berthé, Valérie, et al.
Published: (2025)

Effective Computation of Generalized Abelian Complexity for Pisot Type Substitutive Sequences
by: Couvreur, Jean-Michel, et al.
Published: (2025)

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

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

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

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

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

Decidability of membership problems for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ and singular matrices
by: Diekert, Volker, et al.
Published: (2019)

Dorst-Smeulders Coding for Arbitrary Binary Words
by: De Luca, Alessandro, et al.
Published: (2025)

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

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

Words with factor complexity $2n+1$ and minimal critical exponent
by: Currie, James D.
Published: (2025)

Deciding Sparseness of Regular Languages of Finite Trees and Infinite Words
by: Eickmeyer, Kord, et al.
Published: (2025)

The Shortest Interesting Binary Words
by: Fici, Gabriele
Published: (2024)

Mapped Exponent and Asymptotic Critical Exponent of Words
by: Foster, Eva, et al.
Published: (2025)

The Word Problem for Finitary Automaton Groups
by: Kotowsky, Maximilian, et al.
Published: (2023)

Hypernode Automata
by: Bartocci, Ezio, et al.
Published: (2023)

Group Actions and Some Combinatorics on Words with $\mathbf{vtm}$
by: Machacek, John
Published: (2025)

Hexagonal Picture Scanning Automata
by: D, Deepalakshmi, et al.
Published: (2025)

A Connection Between Unbordered Partial Words and Sparse Rulers
by: Saarela, Aleksi, et al.
Published: (2024)

On Graph Grammars and Games
by: Vijayakumar, Jayakrishna, et al.
Published: (2024)

A substitution lemma for multiple context-free languages
by: Duncan, Andrew, et al.
Published: (2025)

A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
by: German, Samuel
Published: (2026)

A Formalization of Co-Transcriptional Splicing as an Operation on Formal Languages
by: Cho, Da-Jung, et al.
Published: (2025)