Regularity conjecture for finite-state string machines without a meta-vertex

Let a string machine be composed only of finite-state transducers, with the input and output categories of each transducer being tape categories. Suppose it has one free input XXX\to X in a tape category X\mathcal{X} whose generating morphisms form a set Σ\Sigma and are all endomorphisms of the generating object XX. Assume its sole output is a state space S(A)S(A), with some subset designated as accepting. An endomorphism XXX\to X in X\mathcal{X} that contains no instances of the copy morphism is regarded as a string over Σ\Sigma. Regularity conjecture. Every language over Σ\Sigma accepted by this string machine is regular. The conjecture asserts that finite-state string machines without a meta-vertex have no more language-recognition power than finite automata; the paper presents a sketch intended to establish it, but the supplied text gives no resolution status.

Sources & referencesView supporting material

Primary source

Nur Cataltepe and Vanessa Kosoy, “Time complexity for deterministic string machines”, arXiv:2405.06043 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.