Cover Image

State Complexity of Multiple Concatenation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jirásek, Jozef, Jirásková, Galina
Format:	Preprint
Published:	2025
Subjects:	Formal Languages and Automata Theory 68QXX
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Store Languages of Turing Machines and Counter Machines
by: Friesen, Noah, et al.
Published: (2025)

Operational State Complexity of Block Languages
by: Duarte, Guilherme, et al.
Published: (2024)

On the Representation and State Complexity of Block Languages
by: Duarte, Guilherme, et al.
Published: (2024)

Shape Preserving Tree Transducers
by: Gallot, Paul, et al.
Published: (2025)

From regular expressions to deterministic finite automata: $2^{\frac{n}{2}+\sqrt{n}(\log n)^{Θ(1)}}$ states are necessary and sufficient
by: Martynova, Olga, et al.
Published: (2025)

A hierarchy of reversible finite automata
by: Radionova, Maria, et al.
Published: (2024)

On Computational Completeness of Semi-Conditional Matrix Grammars
by: Fernau, Henning, et al.
Published: (2024)

Nondeterministic tree-walking automata are not closed under complementation
by: Martynova, Olga, et al.
Published: (2024)

A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata
by: Petrov, Semyon, et al.
Published: (2024)

Mostowski Index via extended register games
by: Idir, Olivier, et al.
Published: (2024)

An $L^{\#}$ Based Algorithm for Active Learning of Minimal Separating Automata
by: Laumen, Jasper, et al.
Published: (2026)

Bounded Languages Described by GF(2)-grammars
by: Makarov, Vladislav
Published: (2019)

Linear equations and recursively enumerable sets
by: Honkala, Juha
Published: (2024)

A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group
by: Zhu, Yinfeng
Published: (2024)

Around Don's conjecture for binary completely reachable automata
by: Zhu, Yinfeng
Published: (2024)

Don's conjecture for binary completely reachable automata: an approach and its limitations
by: Casas, David, et al.
Published: (2023)

On a homotopy formula for generalized steady Stokes' operators, associated with the de Rham complex
by: Kiseleva, Ulita, et al.
Published: (2026)

Computational Complexity of Alignments
by: Schwanen, Christopher T., et al.
Published: (2026)

A generalization of Deterministic Finite Automata related to discharging
by: Campbell, John M.
Published: (2025)

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

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

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

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

Subword enumeration up to stack-sorting equivalence
by: Campbell, John M., et al.
Published: (2026)

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

Probabilistic automatic complexity of finite strings
by: Gill, Kenneth
Published: (2024)

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

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

On the Complexity of Language Membership for Probabilistic Words
by: Amarilli, Antoine, et al.
Published: (2025)

Descriptional Complexity of Finite Automata -- Selected Highlights
by: Salomaa, Arto, et al.
Published: (2023)

Regular Expressions with Backreferences on Multiple Context-Free Languages, and the Closed-Star Condition
by: Nogami, Taisei, et al.
Published: (2024)

Fine-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs
by: Drabik, Karolina, et al.
Published: (2025)

Star Complexity of Parikh Images of Languages over Infinite Alphabets
by: Danieli, Yoav
Published: (2026)

A Complexity Bound for Determinisation of Min-Plus Weighted Automata
by: Almagor, Shaull, et al.
Published: (2026)

On the Complexity of Computing the Co-lexicographic Width of a Regular Language
by: Becker, Ruben, et al.
Published: (2024)

Unconditional Time and Space Complexity Lower Bounds for Intersection Non-Emptiness
by: Wehar, Michael
Published: (2025)

Waiting Nets: State Classes and Taxonomy
by: Hélouët, Loïc, et al.
Published: (2022)

Bandwidth of Nondeterministic Finite Automata
by: Cho, Da-Jung, et al.
Published: (2026)

Semidirect Product Decompositions for Periodic Regular Languages
by: Inoue, Yusuke, et al.
Published: (2024)

Mind the Gap: A Formal Investigation of the Relationship Between Log and Model Complexity -- Extended Version
by: Schalk, Patrizia, et al.
Published: (2025)