Cover Image

The complexity of finite smooth words over binary alphabets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cassaigne, Julien, Henry, Raphaël
Format:	Preprint
Published:	2026
Subjects:	Formal Languages and Automata Theory Combinatorics Dynamical Systems
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Reduced complexities for sequences over finite alphabets
by: Campbell, John M., et al.
Published: (2025)

Maximal 2-dimensional binary words of bounded degree
by: Massé, Alexandre Blondin, et al.
Published: (2025)

Low complexity binary words avoiding $(5/2)^+$-powers
by: Currie, James, et al.
Published: (2025)

$2$-word-$π$-representable Graphs
by: Adamson, Duncan, et al.
Published: (2026)

Watson-Crick conjugates of words and languages
by: Mahalingam, Kalpana, et al.
Published: (2022)

On a sequence of Kimberling and its relationship to the Tribonacci word
by: Dvořáková, Lubomíra, et al.
Published: (2025)

Symbols frequencies in the Thue--Morse word in base $3/2$ and related conjectures
by: Cassaigne, Julien, et al.
Published: (2026)

Sequential densities of rational languages
by: Gorman, Alexi Block, et al.
Published: (2026)

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

Rule-based Generation of de Bruijn Sequences: Memory and Learning
by: Muñoz, Francisco J., et al.
Published: (2025)

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

A pumping-like lemma for languages over infinite alphabets
by: Danieli, Yoav
Published: (2025)

Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fields
by: Bell, Jason P., et al.
Published: (2022)

Computing the k-binomial complexity of generalized Thue--Morse words
by: Golafshan, M., et al.
Published: (2024)

The reflection complexity of sequences over finite alphabets
by: Allouche, Jean-Paul, et al.
Published: (2024)

On the piecewise complexity of words
by: Schnoebelen, Philippe, et al.
Published: (2024)

Asymptotic bounds for the number of closed and privileged words
by: Gabric, Daniel
Published: (2022)

On a Constraint on Invariant Measures of Certain Cellular Automata
by: Tal, Matan
Published: (2026)

Arithmetical subword complexity of automatic sequences
by: Konieczny, Jakub, et al.
Published: (2023)

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

Mapping words to powers by morphisms
by: Saarela, Aleksi
Published: (2025)

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

Escape of mass of the Thue-Morse sequence
by: Nesharim, Erez, et al.
Published: (2025)

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

On the transversals of Latin squares generated by nonlinear bipermutive cellular automata
by: Dennunzio, Alberto, et al.
Published: (2026)

Half-flips are 5-avoidable
by: Ochem, Pascal
Published: (2026)

Jumbled Scattered Factors
by: Fleischmann, Pamela, et al.
Published: (2025)

Synchronization of strongly connected partial DFAs and prefix codes
by: Berlinkov, Mikhail V., et al.
Published: (2021)

From the Lyndon factorization to the Canonical Inverse Lyndon factorization: back and forth
by: Bonizzoni, Paola, et al.
Published: (2024)

Word-Representable Graphs and Locality of Words
by: Böll, Philipp, et al.
Published: (2025)

Balanced Fibonacci word rectangles, and beyond
by: Shallit, Jeffrey, et al.
Published: (2025)

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

Universality in computable dynamical systems: Old and new
by: González-Prieto, Ángel, et al.
Published: (2025)

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

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

The complexity of reachability problems in strongly connected finite automata
by: Kiefer, Stefan, et al.
Published: (2025)

Deterministic Parikh automata on infinite words
by: Grobler, Mario, et al.
Published: (2024)

On the Completeness and Ordering of Path-Complete Barrier Functions
by: Anand, Mahathi, et al.
Published: (2025)

On asymptotically automatic sequences
by: Konieczny, Jakub
Published: (2023)

Limit dynamics of elementary cellular automaton 18
by: Sabrié, Hervé, et al.
Published: (2023)