Cover Image

A Sharper Upper Bound for the Separating Words Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Dumitru, Bogdan C.
Format:	Preprint
Published:	2025
Subjects:	Formal Languages and Automata Theory Number Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Recursive Prime Factorizations: Dyck Words as Numbers
by: Childress, Ralph L.
Published: (2021)

Completing the picture for the Skolem Problem on order-4 linear recurrence sequences
by: Bacik, Piotr
Published: (2024)

Exact Separation of Words via Trace Geometry
by: Chen, Zeyu, et al.
Published: (2026)

State Complexity of Shifts of the Fibonacci Word
by: Moradi, Delaram, et al.
Published: (2026)

New properties of the $φ$-representation of integers
by: Shallit, Jeffrey, et al.
Published: (2025)

S-unit equations in modules and linear-exponential Diophantine equations
by: Dong, Ruiwen, et al.
Published: (2025)

On the Separability Problem of VASS Reachability Languages
by: Keskin, Eren, et al.
Published: (2024)

The Narayana Morphism and Related Words
by: Shallit, Jeffrey
Published: (2025)

Consecutive Power Occurrences in Sturmian Words
by: Bell, Jason, et al.
Published: (2024)

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

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

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

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

Classifying Words with 3-sort Automata
by: Jastrząb, Tomasz, et al.
Published: (2024)

Reversible Transducers over Infinite Words
by: Dartois, Luc, et al.
Published: (2024)

Characterization of Isometric Words based on Swap and Mismatch Distance
by: Anselmo, M., et al.
Published: (2024)

Measure Many Quantum Finite Automata on Infinite Words
by: Midya, Abhisek, et al.
Published: (2026)

On Normality and Equidistribution for Separator Enumerators
by: Pulari, Subin
Published: (2026)

Separability and Non-Determinizability of WSTS
by: Czerwiński, Wojciech, et al.
Published: (2023)

Bounded treewidth, multiple context-free grammars, and downward closures
by: Aiswarya, C., et al.
Published: (2025)

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

A Tree Sampler for Bounded Context-Free Languages
by: Considine, Breandan
Published: (2024)

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

An 'Experimental Mathematics' Approach to Stolarsky Interspersions via Automata Theory
by: Shallit, Jeffrey
Published: (2025)

The Tribonacci constant and finite automata
by: Shallit, Jeffrey
Published: (2025)

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

Algebraic power series and their automatic complexity modulo prime powers
by: Rowland, Eric, et al.
Published: (2024)

Using finite automata to compute the base-$b$ representation of the golden ratio and other quadratic irrationals
by: Barnoff, Aaron, et al.
Published: (2024)

Proving Properties of $φ$-Representations with the Walnut Theorem-Prover
by: Shallit, Jeffrey
Published: (2023)

Languages of Boundedly-Ambiguous Vector Addition Systems with States
by: Czerwiński, Wojciech, et al.
Published: (2025)

Inform: From Compartmental Models to Stochastic Bounded Counter Machines
by: Leys, Tim, et al.
Published: (2024)

Approximate Problems for Finite Transducers
by: Filiot, Emmanuel, et al.
Published: (2025)

Saturation Problems for Families of Automata
by: Bohn, León, et al.
Published: (2025)

The Expansion Problem for Infinite Trees
by: Blumensath, Achim
Published: (2023)

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

The Similarity Control Problem with Required Events
by: Wang, Yu, et al.
Published: (2026)

Resynchronized Uniformization and Definability Problems for Rational Relations
by: Löding, Christof, et al.
Published: (2021)

Undecidability of the Emptiness Problem for Weak Models of Distributed Computing
by: Principato, Flavio T., et al.
Published: (2025)

Uniform Membership for Hyperedge Replacement Grammars and Related Decision Problems
by: Pshenitsyn, Tikhon
Published: (2025)

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