Regularity conjecture for finite-state string machines without a meta-vertex
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 in a tape category whose generating morphisms form a set and are all endomorphisms of the generating object . Assume its sole output is a state space , with some subset designated as accepting. An endomorphism in that contains no instances of the copy morphism is regarded as a string over . Regularity conjecture. Every language over 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.