Deterministic Suffix-reading Automata

B Srivathsan; R Keerthan; R Venkatesh; Sagar Verma

arxiv: 2505.09353 · v5 · submitted 2025-05-14 · 💻 cs.FL

Deterministic Suffix-reading Automata

R Keerthan , B Srivathsan , R Venkatesh , Sagar Verma This is my paper

Pith reviewed 2026-05-22 15:34 UTC · model grok-4.3

classification 💻 cs.FL

keywords deterministic automatasuffix-reading automataNP-completenessregular languagesautomata minimizationsuccinct representationsDFA-to-DSA conversion

0 comments

The pith

Deciding whether a regular language has an equivalent DSA of total-size at most k is NP-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces deterministic suffix-reading automata (DSAs), a model in which transitions are labeled by words and fire whenever the current input ends with that word as a suffix, allowing the automaton to advance over variable-length blocks rather than single letters. Because label lengths affect the representation, the authors adopt total-size (states plus edges plus summed label lengths) as the size measure instead of state count alone. They give an explicit DFA-to-DSA conversion yet observe that the smallest DSA obtained from the canonical minimal DFA need not be minimal for the language. The central technical result is that, given a DFA and an integer k, deciding existence of an equivalent DSA whose total-size is at most k is NP-complete.

Core claim

Given a DFA and a number k, deciding whether there exists an equivalent DSA of total-size at most k is NP-complete.

What carries the argument

Deterministic suffix-reading automaton: a deterministic finite automaton whose transitions are labeled by nonempty words and fire on any input suffix matching the label, thereby processing the word in variable-length blocks.

If this is right

DSAs can represent some regular languages with strictly smaller total-size than any DFA.
A minimal DSA for a language need not arise by converting its minimal DFA.
Any upper bound obtained from the canonical DFA-to-DSA conversion may be strictly larger than the true minimal total-size.
The minimization problem for DSAs under total-size is at least as hard as the NP-complete decision problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Search procedures for minimal DSAs must explore candidate suffix labels rather than only the states of the input DFA.
For practical construction of small DSAs, approximation or heuristic algorithms become necessary once the input DFA grows large.
The same hardness pattern may appear when studying succinctness of other automata that advance by matching variable-length patterns rather than single symbols.

Load-bearing premise

The total-size measure that adds states, edges, and the summed lengths of all transition labels is the right way to compare succinctness of DSAs with DFAs.

What would settle it

A polynomial-time algorithm that, given any DFA and k, either outputs an equivalent DSA of total-size at most k or correctly reports that none exists.

read the original abstract

We introduce deterministic suffix-reading automata (DSA), a new automaton model over finite words. Transitions in a DSA are labeled with words. From a state, a DSA triggers an outgoing transition on seeing a word ending with the transition's label. Therefore, rather than moving along an input word letter by letter, a DSA can jump along blocks of letters, with each block ending in a suitable suffix. This feature allows DSAs to recognize regular languages more concisely, compared to DFAs. In this work, we focus on questions around finding a minimal DSA for a regular language. In this context, the number of states is not a faithful measure of the size of a DSA, since the transition-labels contain strings of arbitrary length. Hence, we consider total-size (number of states + number of edges + total length of transition-labels) as the size measure of DSAs. We start by formally defining the model and providing a DSA-to-DFA conversion that allows to compare the expressiveness and succinctness of DSA with related automata models. Our main technical contribution is a method to derive DSAs from a given DFA: a DFA-to-DSA conversion. We make a surprising observation that the smallest DSA derived from the canonical DFA of a regular language L need not be a minimal DSA for L. This observation leads to a fundamental bottleneck in deriving a minimal DSA for a regular language. In fact, we prove that given a DFA and a number k, the problem of deciding if there exists an equivalent DSA of total-size atmost k is NP-complete.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper introduces suffix-reading automata that can be more succinct than DFAs for regular languages, gives a DFA-to-DSA conversion, notes that canonical-derived ones are not always minimal, and claims NP-completeness for total-size minimization, though the NP membership direction needs checking on k encoding.

read the letter

The main takeaway is that the authors define deterministic suffix-reading automata, show how to build them from DFAs, note that the obvious construction does not always give the smallest one, and prove that deciding if a small enough DSA exists is NP-complete. The DSA model is new, as is the specific observation about non-minimality from the canonical DFA and the complexity result for total-size minimization. The paper does well in providing a formal definition and a conversion that lets you compare succinctness with DFAs. This gives a concrete way to see when DSAs can be smaller. The total-size measure makes sense because transition labels can be arbitrary strings, so just counting states would miss the cost. The NP-completeness is the strongest claim, but the stress-test concern about certificate size is worth checking. If k is in binary, a DSA with total-size k could require exponential bits to describe, so standard NP verification would not work in polynomial time. The abstract does not mention unary encoding or an alternative verifier, so the full paper needs to clarify this or the membership direction may not hold. The work is straightforward and stays within automata theory without loose ends in the abstract. No invented entities beyond the new model, and no free parameters. This paper is for people in formal languages who care about alternative automaton models and their minimization. A reader who follows papers on succinct automata would get something out of the constructions and the hardness result. It deserves a serious referee because the new model and the complexity proof are substantive enough to warrant review, even if revisions are needed on the NP argument. I recommend sending it to peer review.

Referee Report

2 major / 2 minor

Summary. The paper introduces deterministic suffix-reading automata (DSAs), a model in which transitions are labeled by words and fire upon reading any input suffix that ends with the label. This allows DSAs to recognize regular languages more succinctly than DFAs by jumping over blocks. The authors give a DSA-to-DFA conversion, a DFA-to-DSA conversion, observe that the smallest DSA derived from the canonical DFA of L need not be minimal for L, and prove that, given a DFA A and integer k, deciding whether an equivalent DSA of total-size (states + edges + total label length) at most k exists is NP-complete.

Significance. If the central claims hold, the work adds a new succinctness measure and model to the automata-theory literature on regular-language representations. The NP-completeness result would be a concrete complexity classification for minimization under the chosen total-size measure. The observation that canonical-DFA-derived DSAs are not necessarily minimal is a useful negative result that blocks naive minimization approaches.

major comments (2)

[NP-completeness proof / decision problem statement] Proof of NP membership (the decision problem stated in the abstract and presumably formalized in the complexity section): membership in NP requires a polynomial-time verifier and polynomially sized certificates. The natural certificate is a DSA whose total-size is ≤ k. When k is encoded in binary (the default encoding), k can be exponential in |A|, making the certificate description length Θ(k) and therefore exponential in the input length. No polynomial verifier can read such a certificate. The manuscript gives no indication that k is required to be unary, nor does it supply an alternative verification procedure that avoids materializing the full DSA.
[DFA-to-DSA conversion and minimality observation] § on DFA-to-DSA conversion and the observation that the smallest DSA derived from the canonical DFA need not be minimal: this observation is presented as a 'fundamental bottleneck.' The manuscript must show explicitly that the total-size of the derived DSA can be strictly larger than the minimal DSA for the same language; otherwise the observation does not block a polynomial-time minimization procedure and weakens the motivation for the subsequent NP-completeness claim.

minor comments (2)

[Introduction / size measure] The total-size measure (states + edges + sum of label lengths) is introduced without a formal definition or comparison table against other succinctness measures (e.g., NFA size, DFA state count). A short table or paragraph would clarify why this measure is natural for DSAs.
[Abstract] The abstract states the main results but supplies no proof sketches, small examples, or complexity reductions. Adding a one-paragraph proof outline or a concrete 3-state DFA example with its minimal DSA would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable comments on the NP-completeness proof and the minimality observation. We address each major comment point by point below.

read point-by-point responses

Referee: Proof of NP membership (the decision problem stated in the abstract and presumably formalized in the complexity section): membership in NP requires a polynomial-time verifier and polynomially sized certificates. The natural certificate is a DSA whose total-size is ≤ k. When k is encoded in binary (the default encoding), k can be exponential in |A|, making the certificate description length Θ(k) and therefore exponential in the input length. No polynomial verifier can read such a certificate. The manuscript gives no indication that k is required to be unary, nor does it supply an alternative verification procedure that avoids materializing the full DSA.

Authors: We thank the referee for pointing out this subtlety in the complexity analysis. Upon reflection, the manuscript does not specify the encoding of k. To place the problem in NP, we will revise the paper to state that k is encoded in unary. In this case, the size of the input is Ω(k), so a certificate of size O(k) is polynomial. The verifier can then check that the provided DSA has total-size at most k and that it is equivalent to the input DFA, which can be verified in polynomial time by converting the DSA to a DFA and comparing the languages. revision: yes
Referee: § on DFA-to-DSA conversion and the observation that the smallest DSA derived from the canonical DFA need not be minimal: this observation is presented as a 'fundamental bottleneck.' The manuscript must show explicitly that the total-size of the derived DSA can be strictly larger than the minimal DSA for the same language; otherwise the observation does not block a polynomial-time minimization procedure and weakens the motivation for the subsequent NP-completeness claim.

Authors: We agree that providing an explicit example would make the observation more concrete and better justify the 'fundamental bottleneck' claim. In the revised version, we will include a specific regular language and two DSAs: one derived from the canonical DFA with a certain total-size, and another equivalent DSA with strictly smaller total-size. This example will demonstrate that the canonical derivation does not always yield the minimal DSA, thereby strengthening the motivation for studying the NP-complete minimization problem. revision: yes

Circularity Check

0 steps flagged

No circularity: NP-completeness claim rests on independent reductions

full rationale

The paper defines DSA, gives a DFA-to-DSA conversion, notes that the minimal DSA need not come from the canonical DFA, and then states that the decision problem is NP-complete. None of these steps reduce to self-definition, fitted parameters renamed as predictions, or load-bearing self-citations. The complexity result is presented as following from standard automata constructions and a reduction; no equation or central claim is shown to be equivalent to its inputs by construction. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper introduces a new automaton model and relies on standard background from automata theory; no free parameters are fitted and no new physical entities are postulated.

axioms (1)

standard math Every regular language is recognized by some DFA
Standard result from automata theory used to compare DSA and DFA expressiveness.

invented entities (1)

Deterministic Suffix-reading Automaton (DSA) no independent evidence
purpose: To recognize regular languages more concisely by triggering transitions on suffix matches rather than single letters
New model defined in the paper; no independent evidence outside the definitions and constructions is provided.

pith-pipeline@v0.9.0 · 5815 in / 1245 out tokens · 43045 ms · 2026-05-22T15:34:04.277686+00:00 · methodology

Deterministic Suffix-reading Automata

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)