arxiv: 2604.11567 · v1 · submitted 2026-04-13 · 💻 cs.FL

Recognition: no theorem link

Minimizing Streaming String Transducers: An algebraic approach

Nathan Lhote, Pierre-Alain Reynier, Yahia Idriss Benalioua

Authors on Pith no claims yet

Pith reviewed 2026-05-10 16:12 UTC · model grok-4.3

classification 💻 cs.FL

keywords streaming string transducersbimachinesminimizationNP-completenessrational functionsalgebraic methodsformal languagestransducers

0 comments

The pith

A bijection between a subclass of appending streaming string transducers and bimachines enables polynomial-time register minimization.

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

The paper establishes a direct correspondence between a restricted form of appending streaming string transducers and bimachines that translates the transducer's states and registers into two parameters of the bimachine. This correspondence allows applying known minimization algorithms for bimachines, resulting in an efficient procedure for reducing the number of registers and a harder but feasible procedure for reducing both states and registers. To handle the full class of transducers, the authors introduce asynchronous bimachines that extend the correspondence. They further establish that minimizing registers while keeping the underlying automaton fixed is NP-complete.

Core claim

We show a bijection between a subclass of aSST and bimachines, which maps the numbers of states and registers of the aSST to two natural parameters of the bimachine. Using known results on the minimization of bimachines, this yields a Ptime (resp. NP) procedure to minimize this subclass of aSST with respect to registers (resp. both states and registers). In a second step, we introduce a new model of bimachines, named asynchronous bimachines, which allows to lift the bijection to the whole class of aSST. Based on this, we prove that register minimization with a fixed underlying automaton is NP-complete.

What carries the argument

The bijection from a subclass of appending streaming string transducers to bimachines, which equates the transducer's state and register counts to bimachine parameters.

If this is right

Minimizing the number of registers in the subclass of aSST can be done in polynomial time.
Minimizing both the number of states and registers in the subclass is NP.
Register minimization for aSST with a fixed underlying automaton is NP-complete for the full class.
Asynchronous bimachines provide a way to represent the full class of aSST algebraically.

Where Pith is reading between the lines

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

This algebraic approach could be used to develop practical tools for optimizing string processing functions in applications like data streaming or text transformation.
The NP-completeness result highlights the inherent difficulty in jointly minimizing states and registers without additional constraints.
Similar reductions might apply to minimization problems for other models of transducers or functions.

Load-bearing premise

The bijection between the subclass of aSST and bimachines preserves the exact minimal numbers of states and registers without adding or losing minimal representations.

What would settle it

A specific aSST in the subclass for which an independently minimized version has fewer registers than what the corresponding minimal bimachine predicts.

Figures

Figures reproduced from arXiv: 2604.11567 by Nathan Lhote, Pierre-Alain Reynier, Yahia Idriss Benalioua.

**Figure 2.** Figure 2: An aSST with a fixed output register and dependant flows. Barring some considerations concerning the domains, this restriction, in conjunction with the fixed output register assumption, allows us to show a one-to-one correspondence between the aSST verifying these conditions and the bimachines realizing the same transduction. In the following, we consider the class of aSST that have independent flows, and… view at source ↗

**Figure 3.** Figure 3: A bimachine Example 5. Let Σ = Γ = {a, b} and consider the bimachine B = (L, R, λ, ω, ρ) whose automata are depicted on [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗

**Figure 4.** Figure 4: A run of a bimachine [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗

**Figure 5.** Figure 5: Input: Run of L: Input of R: Run of R: Output: li la la la la li la la la rb rb rb rb rf a b a b a b a b ϵ b b a a ϵ [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗

read the original abstract

In this work, we study minimization of rational functions given as appending streaming string transducers (aSST for short). We rely on an algebraic presentation of these functions, known as bimachines, to address the minimization of both states and registers of aSST. First, we show a bijection between a subclass of aSST and bimachines, which maps the numbers of states and registers of the aSST to two natural parameters of the bimachine. Using known results on the minimization of bimachines, this yields a Ptime (resp. NP) procedure to minimize this subclass of aSST with respect to registers (resp. both states and registers). In a second step, we introduce a new model of bimachines, named asynchronous bimachines, which allows to lift the bijection to the whole class of aSST. Based on this, we prove that register minimization with a fixed underlying automaton 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 links a subclass of appending SSTs to bimachines via a bijection for minimization and uses asynchronous bimachines for the full class, plus proves NP-completeness for fixed-automaton register minimization.

read the letter

The key point here is that the authors give a bijection between a subclass of appending streaming string transducers and bimachines that maps the numbers of states and registers to two natural parameters of the bimachine. This lets them import existing minimization results for bimachines to get polynomial time for register minimization and NP for joint state-register minimization on that subclass. They then define asynchronous bimachines to cover the full class and use that to prove NP-completeness for register minimization when the underlying automaton is fixed. What stands out as new is the specific bijection and the asynchronous bimachine model, which extends the algebraic approach beyond the subclass. The NP-completeness result for the fixed-automaton case is also a solid addition, as it shows the problem is hard even with some structure fixed. The paper does well by grounding the work in known bimachine theory rather than starting from scratch, which keeps the proofs more manageable and connects to prior work on rational functions. The soft spots are mostly around the details of the constructions. The bijection needs to accurately map the realized functions without losing or adding behaviors, and the asynchronous extension must not introduce extraneous outputs. The actual proofs would need close reading to confirm no gaps in the equivalence. The NP-completeness reduction probably comes from some known hard problem in automata, but its applicability to aSST should be verified for edge cases. This paper is aimed at people working on transducer minimization and algebraic characterizations of string transformations. A reader interested in streaming applications or formal methods for string processing would get value from the algorithms and complexity results. It deserves a serious referee because the claims are specific, build on established results, and include a hardness proof that could be useful for future work. I would recommend sending it to peer review. The algebraic angle is clean and the results seem worth checking in detail.

Referee Report

0 major / 3 minor

Summary. The paper studies minimization of rational functions represented as appending streaming string transducers (aSST). It establishes a bijection between a subclass of aSST and bimachines that maps the numbers of states and registers to bimachine parameters. This allows importing known bimachine minimization results to obtain a Ptime algorithm for register minimization and an NP procedure for joint state-and-register minimization on the subclass. The authors introduce asynchronous bimachines to extend the bijection to the full class of aSST and prove that register minimization with a fixed underlying automaton is NP-complete.

Significance. If the bijection and asynchronous-bimachine extension are correct, the work provides a valuable algebraic bridge between streaming transducers and bimachines, yielding concrete algorithmic procedures and a complexity classification for minimization problems. The explicit mapping of resource parameters and the use of existing bimachine results are strengths; the NP-completeness result for the fixed-automaton case is a clear contribution to the theory of transducers.

minor comments (3)

[Abstract] Abstract: the subclass of aSST to which the bijection applies is not characterized explicitly; a short sentence defining or naming the subclass would improve readability and scope clarity.
The definition and semantics of asynchronous bimachines should include a brief comparison (e.g., via a small example or table) with standard bimachines to make the extension's necessity and correctness immediately apparent.
Ensure that the NP-completeness reduction is accompanied by a clear statement of the source problem and how the fixed-automaton constraint is encoded, to facilitate verification of the hardness argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work and the recommendation for minor revision. The report correctly identifies the bijection between a subclass of appending streaming string transducers and bimachines, the resulting polynomial-time and NP procedures, and the extension via asynchronous bimachines that yields the NP-completeness result for register minimization with a fixed underlying automaton. Since the report lists no specific major comments, we have no points requiring rebuttal or revision at this stage.

Circularity Check

0 steps flagged

No significant circularity; derivation uses external results and independent constructions

full rationale

The paper's central steps consist of exhibiting an explicit bijection between a subclass of aSST and bimachines (mapping states/registers to bimachine parameters while preserving the realized function), invoking known external minimization results for bimachines to obtain PTime/NP procedures, and defining a new asynchronous-bimachine model to lift the correspondence to the full aSST class. The NP-completeness proof for register minimization under a fixed automaton follows from a reduction within this framework. None of these steps is self-definitional, none renames a fitted parameter as a prediction, and the cited bimachine results are external rather than self-citations whose validity depends on the present work. The algebraic constructions are presented as independent and verifiable against the transducer semantics, rendering the derivation self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work relies on standard algebraic presentations of bimachines and known minimization results; no free parameters are introduced, and the new asynchronous bimachine is an extension rather than an invented entity with independent evidence.

axioms (1)

domain assumption Known results on bimachine minimization are correct and applicable.
The paper invokes these results to obtain the Ptime and NP procedures for the subclass.

invented entities (1)

asynchronous bimachines no independent evidence
purpose: To lift the bijection from the subclass to the full class of aSST.
New model introduced to handle cases where input and output are not synchronized.

pith-pipeline@v0.9.0 · 5457 in / 1201 out tokens · 63345 ms · 2026-05-10T16:12:58.478675+00:00 · methodology

discussion (0)

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Minimization of Streaming Transducers
cs.FL 2026-05 unverdicted novelty 7.0

General criteria for minimal models of streaming transducers are established, yielding effective minimization for variants of streaming string-to-tree transducers that build terms at leaves or roots.
Minimization of Streaming Transducers
cs.FL 2026-05 unverdicted novelty 6.0

General criteria for the existence of minimal models of streaming transducers are provided, with effective minimization results for variants of streaming string-to-tree transducers.

Reference graph

Works this paper leans on

21 extracted references · 13 canonical work pages · cited by 1 Pith paper

[1]

In: Lodaya, K., Mahajan, M

Alur, R., Cerný, P.: Expressiveness of streaming string transducers. In: Lodaya, K., Mahajan, M. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India. LIPIcs, vol. 8, pp. 1–12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010). https://doi.org/10.423...

work page doi:10.4230/lipics.fsttcs.2010.1 2010
[2]

In: Ball, T., Sagiv, M

Alur, R., Cerný, P.: Streaming transducers for algorithmic verification of single- pass list-processing programs. In: Ball, T., Sagiv, M. (eds.) Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011. pp. 599–610. ACM (2011). https://doi.org/10.1145/1926385.1926454

work page doi:10.1145/1926385.1926454 2011
[3]

In: 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013

Alur, R., D’Antoni, L., Deshmukh, J.V., Raghothaman, M., Yuan, Y.: Regular functions and cost register automata. In: 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013. pp. 13–22. IEEE Computer Society (2013). https://doi.org/10.1109/LICS.2013.65

work page doi:10.1109/lics.2013.65 2013
[4]

Benalioua, N

Benalioua, Y.I., Lhote, N., Reynier, P.: Minimizing cost register automata over a field. In: Královic, R., Kucera, A. (eds.) 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia. LIPIcs, vol. 306, pp. 23:1–23:15. Schloss Dagstuhl - Leibniz- Zentrum für Informatik (2024). https://...

work page doi:10.4230/lipics.mfcs.2024.23 2024
[5]

Berstel, J.: Transductions and Context-Free Languages, Teubner Studienbücher : Informatik, vol. 38. Teubner (1979), https://www.worldcat.org/oclc/06364613

work page arXiv 1979
[6]

Berstel, J., Boasson, L.: Transductions and context-free languages. Ed. Teubner pp. 1–278 (1979)

1979
[7]

Zeitschrift für Mathematische Logik und Grundlagen der Mathematik6(1–6), 66–92 (1960)

Büchi, J.R.: Weak second-order arithmetic and finite automata. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik6(1–6), 66–92 (1960)

1960
[8]

Daviaud, P.-A

Daviaud, L., Reynier, P.A., Talbot, J.M.: A generalised twinning property for min- imisation of cost register automata. In: Grohe, M., Koskinen, E., Shankar, N. (eds.) Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Sci- ence, LICS ’16, New York, NY, USA, July 5-8, 2016. pp. 857–866. ACM (2016). https://doi.org/10.1145/2933575.2934549

work page doi:10.1145/2933575.2934549 2016
[9]

Volume A, Pure and Ap- plied Mathematics, vol

Eilenberg, S.: Automata, Languages, and Machines. Volume A, Pure and Ap- plied Mathematics, vol. A. Academic Press (1974), https://www.worldcat.org/ oclc/310535248

work page arXiv 1974
[10]

In Transactions of the American Mathematical Society98(1), 21–51 (1961)

Elgot, C.C.: Decision problems of finite automata design and related arithmetics. In Transactions of the American Mathematical Society98(1), 21–51 (1961)

1961
[11]

Logical Methods in Computer Science15(4) (2019)

Filiot,E.,Gauwin,O.,Lhote,N.:Logicalandalgebraiccharacterizationsofrational transductions. Logical Methods in Computer Science15(4) (2019). https://doi. org/10.23638/LMCS-15(4:16)2019

work page doi:10.23638/lmcs-15(4:16)2019 2019
[12]

In: Raman, V., Suresh, S.P

Filiot, E., Krishna, S.N., Trivedi, A.: First-order definable string transformations. In: Raman, V., Suresh, S.P. (eds.) 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India. LIPIcs, vol. 29, pp. 147–159. Schloss Dagstuhl - Leibniz-ZentrumfürInformatik(2014...

work page doi:10.4230/lipics.fsttcs 2014
[13]

ACM SIGLOG News3(3), 4–19 (2016)

Filiot, E., Reynier, P.A.: Transducers, logic and algebra for functions of finite words. ACM SIGLOG News3(3), 4–19 (2016). https://doi.org/10.1145/2984450. 2984453 Minimizing Streaming String Transducers: An algebraic approach 15

work page doi:10.1145/2984450 2016
[14]

Filiot, E., Reynier, P.A.: Copyful streaming string transducers. Fundam. Informat- icae178(1–2), 59–76 (2021). https://doi.org/10.3233/FI-2021-1998

work page doi:10.3233/fi-2021-1998 2021
[15]

Computers22(12), 1099–1102 (1973)

Pfleeger,C.P.:Statereductioninincompletelyspecifiedfinite-statemachines.IEEE Trans. Computers22(12), 1099–1102 (1973). https://doi.org/10.1109/T-C.1973. 223655

work page doi:10.1109/t-c.1973 1973
[16]

Acta Informatica22(6), 663–678 (1986)

Reusch, B., Merzenich, W.: Minimal coverings for incompletely specified sequen- tial machines. Acta Informatica22(6), 663–678 (1986). https://doi.org/10.1007/ BF00263650

1986
[17]

Siam Journal On Computing20(4), 669–685 (1991)

Reutenauer, C., Schützenberger, M.P.: Minimization of rational word functions. Siam Journal On Computing20(4), 669–685 (1991). https://doi.org/10.1137/ 0220042

1991
[18]

https://doi.org/10.1016/S0019-9958(61)80006-5

Schützenberger,M.P.:Aremarkonfinitetransducers.Inf.Control.4(2–3),185–196 (1961). https://doi.org/10.1016/S0019-9958(61)80006-5

work page doi:10.1016/s0019-9958(61)80006-5 1961
[19]

Birkhäuser, Boston, Basel and Berlin (1994)

Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston, Basel and Berlin (1994)

1994
[20]

Trakhtenbrot, B.A.: Finite automata and logic of monadic predicates (in Russian). Dokl. Akad. Nauk SSSR140, 326–329 (1961) 16 Y. I. Benalioua et al. A Examples A.1 Example of a bimachine li lb la b a a, b a, b (a) Left automatonL rf rb ra b a, b a a, b (b)RightautomatonR Fig.3: A bimachine Example 5.LetΣ=Γ={a, b}and consider the bimachineB= (L,R, λ, ω, ρ)...

1961
[21]

–o′ is defined, for allu∈Σ ∗ andσ∈Σ, by(q ′ 0 ·A′ u)∗ T ′ σ= (q 0 ·A u)∗ T σif (q0 ·A u)∗ T σis defined and(q ′ 0 ·A′ u)∗ T ′ σ=σotherwise

=i(q 0). –o′ is defined, for allu∈Σ ∗ andσ∈Σ, by(q ′ 0 ·A′ u)∗ T ′ σ= (q 0 ·A u)∗ T σif (q0 ·A u)∗ T σis defined and(q ′ 0 ·A′ u)∗ T ′ σ=σotherwise. It is well-defined since ifq ′ 0 ·A′ u=q ′ 0 ·A′ vfor somev∈Σ ∗ thenu∼ A′ vthusu≈vwhich means that(q 0 ·A u)∗ T σ= (q 0 ·A v)∗ T σ. –f ′ is defined, for allu∈Σ ∗, byf ′(q′ 0 ·A′ u) =f ′(q0 ·A u)ifq 0 ·A u∈Fan...