arxiv: 2604.25619 · v1 · submitted 2026-04-28 · 💻 cs.FL

Recognition: unknown

Decomposition of Automata recognizing Ideals

Isma\"el Jecker, Mathias Berry, Pierre-Cyrille H\'eam

Authors on Pith no claims yet

Pith reviewed 2026-05-07 13:52 UTC · model grok-4.3

classification 💻 cs.FL

keywords automata decompositionideal languagesintersectionunionNL complexitypolynomial-time algorithmregular languagesfinite automata

0 comments

The pith

Automata recognizing ideal languages can be decomposed into intersections or unions of smaller automata, with these decisions decidable in NL and a polynomial-time construction for intersections.

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

The paper establishes that when finite automata recognize ideal languages, which take the form of finite unions of expressions like the set of strings containing a fixed sequence of letters with arbitrary strings in between, it is possible to decide in nondeterministic logspace whether the language equals an intersection or a union of languages accepted by strictly smaller automata. It further supplies an explicit polynomial-time procedure that, when an intersection decomposition exists, outputs the smaller automata and guarantees each one still recognizes an ideal. A reader would care because general-purpose automaton decomposition lacks known efficient algorithms, yet the special pattern structure of ideals renders both the decision and the constructive case tractable, offering a concrete route to smaller representations for this natural subclass of regular languages.

Core claim

We show that the two problems of deciding whether such a language can be decomposed into an intersection or a union of smaller automata are decidable in NL. Moreover, we provide a polynomial-time algorithm that computes a decomposition into an intersection, if one exists, while ensuring that the resulting components also recognize ideal languages.

What carries the argument

Decomposition of an automaton accepting an ideal into smaller automata whose intersection or union exactly recovers the original language, with the intersection case required to preserve ideal acceptance.

If this is right

When an intersection decomposition exists it can be computed in polynomial time and each component remains an ideal recognizer.
Both intersection and union decomposability questions lie in NL, so they admit efficient nondeterministic verification.
Decompositions yield strictly smaller automata for the same ideal language, directly reducing state count.
The ideal-preservation property permits repeated application of the procedure to the resulting components.

Where Pith is reading between the lines

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

The same structural properties of ideals may allow similar decompositions at nearby levels of the language hierarchy.
An implementation of the polynomial algorithm could be run on concrete ideal automata arising in string-processing tasks to measure typical size reduction.
If the NL bound is tight, it would separate these problems from harder general decomposition tasks in automata theory.
The constructive method might combine with existing minimization routines to produce even smaller representations.

Load-bearing premise

The input must be an automaton that exactly recognizes an ideal language, and any intersection decomposition must keep every component within the ideal class.

What would settle it

An automaton accepting a language of the required ideal form for which the NL procedure reports a decomposition exists yet no such smaller automata actually satisfy the intersection or union equality, or for which the polynomial algorithm returns components whose intersection differs from the original language.

read the original abstract

Minimizing the size of finite automata is a fundamental problem in theoretical computer science. Beyond standard minimization, further reductions can be achieved by decomposing an automaton into smaller components whose languages combine via intersection or union to recover the original language. However, in general, no polynomial-time algorithm is known for computing such decompositions. In this paper, we focus on automata that recognize ideals, that is, languages at level 1/2 in the Straubing-Th\'erien hierarchy. Equivalently, these languages are expressible as a finite union of languages of the form $\Sigma^*a_1\Sigma^*\dots\Sigma^*a_n\Sigma^*$ where $\Sigma$ is an alphabet and $a_i$ are letters of $\Sigma$. We show that the two problems of deciding whether such a language can be decomposed into an intersection or a union of smaller automata are decidable in NL. Moreover, we provide a polynomial-time algorithm that computes a decomposition into an intersection, if one exists, while ensuring that the resulting components also recognize ideal languages.

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

This paper shows NL decidability for intersection and union decompositions of ideal automata plus a poly-time construction for the intersection case that stays inside ideals.

read the letter

The main result is that when an automaton recognizes an ideal language, you can decide in NL whether its language decomposes as an intersection or union of smaller automata. They also give a polynomial-time algorithm that finds an intersection decomposition and keeps every piece an ideal too. This is new: the general decomposition problem has no known poly-time solution, and earlier work on the Straubing-Thérien hierarchy did not establish these bounds or the constructive algorithm for level 1/2 languages. The restriction to ideals lets them exploit the concrete form of these languages as finite unions of Σ* a1 Σ* … an Σ* to get clean complexity and an explicit construction. That is the useful part. The paper is clear about its scope. It only claims the results when the input automaton exactly recognizes an ideal, and the construction is required to preserve that property. The NL membership for both problems and the poly-time intersection algorithm follow from the structure of ideals, and nothing in the claims looks circular or overreaches. The soft spots are mostly about reach. The results do not apply outside exact ideals, so they do not help with nearby languages or with decompositions that drop the ideal property. For unions they only give the decision procedure, not a construction like the one for intersections; that asymmetry is fine but limits how far the work goes. The abstract states the claims plainly, and the stress-test finds no internal contradictions or hidden assumptions that would break the argument. This is for people working on automata minimization, decomposition algorithms, or the lower levels of the Straubing-Thérien hierarchy. A reader who needs concrete procedures for ideal languages will get something usable out of it. It deserves peer review because the results are new for this class, the setting is well-motivated, and the claims are sharp enough to be worth checking in detail.

Referee Report

0 major / 3 minor

Summary. The paper focuses on finite automata recognizing ideal languages (level 1/2 of the Straubing-Thérien hierarchy, equivalently finite unions of languages of the form Σ* a1 Σ* ⋯ an Σ*). It claims that the decision problems of whether such a language admits a decomposition into an intersection or a union of smaller automata are both in NL, and gives a polynomial-time algorithm to compute an intersection decomposition (when one exists) such that the component automata also recognize ideals.

Significance. If the claims hold, the work is significant because it identifies a natural, well-studied subclass of regular languages for which both decision and constructive decomposition problems admit low-complexity solutions, in contrast to the general case where no polynomial-time algorithms are known. The NL upper bounds and the P-time constructive procedure that preserves the ideal property constitute concrete algorithmic advances within the Straubing-Thérien hierarchy.

minor comments (3)

[Abstract] Abstract: the parenthetical definition of ideals is clear, but a short concrete example of an ideal language together with a non-trivial intersection decomposition would improve accessibility for readers outside the immediate subfield.
[Section 4] The NL algorithms are described at a high level; an explicit statement of the size of the auxiliary graphs or configurations used in the logspace reductions (e.g., in the sections presenting the decision procedures) would make the complexity claims easier to verify at a glance.
[Introduction] A short paragraph relating the new results to existing work on decomposition or minimization of regular languages (or on other levels of the Straubing-Thérien hierarchy) would help situate the contribution.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the paper and for recommending minor revision. The referee's description of our results on NL decidability for both intersection and union decompositions, as well as the polynomial-time algorithm for ideal-preserving intersection decompositions, is accurate.

Circularity Check

0 steps flagged

No significant circularity; algorithmic results are self-contained

full rationale

The paper establishes NL decidability for intersection and union decomposition problems on automata recognizing ideals (level 1/2 Straubing-Thérien), plus a polynomial-time construction for intersection decompositions that preserve the ideal property. These are decision procedures and explicit algorithms grounded in automata theory, not derivations that reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations. The restriction to exact ideal recognition is stated as part of the problem setup. No equations or steps in the provided claims equate a claimed result to its own inputs via renaming or ansatz smuggling. The derivation chain relies on standard formal-language techniques and is externally falsifiable via automata constructions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard automata theory and the definition of ideal languages as level 1/2 in the Straubing-Thérien hierarchy. No free parameters, invented entities, or ad-hoc axioms are introduced beyond the usual background of regular languages and finite automata.

axioms (2)

domain assumption Ideal languages are exactly the languages at level 1/2 of the Straubing-Thérien hierarchy and can be expressed as finite unions of languages of the form Σ* a1 Σ* … Σ* an Σ*.
This is the central definition used throughout the abstract to restrict the input class.
standard math Standard results on finite automata minimization and language operations (intersection, union) hold.
Implicit background used to talk about decomposition and size reduction.

pith-pipeline@v0.9.0 · 5480 in / 1519 out tokens · 37850 ms · 2026-05-07T13:52:44.884500+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

7 extracted references

[1]

Then either δ(q,u ) ≼δ(q,vu ), or δ(q,u )and δ(q,vu )are incomparable

Let q∈Sand u,v∈Σ∗. Then either δ(q,u ) ≼δ(q,vu ), or δ(q,u )and δ(q,vu )are incomparable. 4.Letq∈Sbe a sink state. IfL(A)̸=∅thenq∈F. Proof. 1. By definition of≼, ifq≼r , then there existsu∈Σ∗such thatr =δ(q,u ). For all w∈R(A,q ), the wordw is a sub-word ofuw. Hence, since ideals are close by upper-words, we haveuw∈R(A,q ). Now, sinceA is deterministic an...
[2]

SinceA is deterministic,uw∈R(A,q )

Let w∈R(A,δ(q,u )). SinceA is deterministic,uw∈R(A,q ). SinceR(A,q )is an ideal, and sinceuw is a sub-word ofvuw, we havevuw∈R(A,q ). Therefore,w∈R(A,δ(q,vu )) asAis deterministic
[3]

If δ(q,vu )̸≼δ(q,u ), the statement is immediately satisfied as eitherδ(q,u ) ≼δ(q,vu )or δ(q,u)̸≼δ(q,vu), and the later case implies thatδ(q,u)andδ(q,vu)are incomparable. Now in the case whereδ(q,vu ) ≼δ(q,u ), on the one hand Item 1 of this property yields that R(A,δ(q,vu ))⊆R(A,δ(q,u )), and on the other hand Item 2 of this property yields that R(A,δ(q...
[4]

Let v∈L(A)

SinceA is trim, there existsw∈Σ∗such thatδ(ι,w) = q. Let v∈L(A). SinceL(A) is an ideal, one haswv∈L(A). And sinceq is a sink state,δ(ι,vw) = q. Those two statements implies thatq∈F. ◀ B Proofs for Section 3 (Intersection-decomposition of non-linear automata) ▶ Proposition 7.Let A = (S, Σ,ι,{qf},δ)be a minimal automaton accepting an ideal. Then Ais non-lin...
[5]

Let w = w1...wrk(q) be the label ofπand let s = δ(ι,w1...wn)

Let πbe a loopfree path fromιto q. Let w = w1...wrk(q) be the label ofπand let s = δ(ι,w1...wn). By definition of ≼ one hass≼q . Then it suffices to show that rk(s) =n. Sinceδ(ι,w1...wn) =s, one hasrk(s) ⩾n . Now, for all wordsw′such that δ(ι,w′) =s, one hasδ(ι,w′wn+1...wk) =q. Therefore, by definition ofrk(q), the word w′wn+1...wk has a length smaller or...
[6]

By definition of the rankrk(δ(ι,u1...uk−1)) = rk(qsep)

Letu =u1...uk be a word such that the run ofA overu fromιleads toρwithout cycle. By definition of the rankrk(δ(ι,u1...uk−1)) = rk(qsep). Sinceqsep is the only state of rank rk(qsep), by Lemma 9,δ(ι,u1...uk−1) =q sep. Thusδ(qsep,uk) =ρ
[7]

Moreover,|Ssep|̸= 0as otherwise ≼ would be a total order onS, contradicting the non-linearity ofA

SinceA is deterministic, the fact that|qsep|⩽|Σ|follows immediately from Item 3. Moreover,|Ssep|̸= 0as otherwise ≼ would be a total order onS, contradicting the non-linearity ofA. Finally,|Ssep|̸= 1since qsep = max{n∈N|∀m⩽n,am = 1}where am =|{s∈S|rk(s) =m}|by Lemma 9. Therefore2⩽|Ssep|⩽|Σ|.◀ ▶ Lemma 24.Let A = (S, Σ,ι,{qf},δ)∈be inI. Letρ∈Ssep, q∈Fam(ρ)an...