A polynomial-time algorithm for the automatic Baire property

Ludwig Staiger

arxiv: 2501.15192 · v2 · submitted 2025-01-25 · 💻 cs.FL

A polynomial-time algorithm for the automatic Baire property

Ludwig Staiger This is my paper

Pith reviewed 2026-05-23 04:54 UTC · model grok-4.3

classification 💻 cs.FL

keywords automatic Baire propertyMuller automatonBüchi automatonpolynomial-time algorithmCantor spacemeagre setsinfinite wordsomega-languages

0 comments

The pith

Given a Muller automaton for an infinite-word language, automata for an open set and a meagre exception realizing the automatic Baire property are constructible in polynomial time.

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

The paper shows that any language recognized by a Muller automaton over the Cantor space admits an automatic Baire decomposition: an open set and a meagre set, both also recognized by automata, such that the original language differs from the open set by a meagre amount. The construction runs in polynomial time and produces sets of simple topological form. For a restricted class of Muller automata the same sets can be recognized by Büchi automata whose size is at most quadratic in the input. A sympathetic reader cares because the result turns an existence statement from topology into an effective, efficient algorithm that stays within the class of finite automata.

Core claim

Given a Muller automaton defining the original set, the open and meagre sets that realize the automatic Baire property can be constructed in polynomial time. Because the constructed sets have simple topological structure, equivalent Büchi automata of at most quadratic size exist for a restricted class of the input Muller automata.

What carries the argument

Polynomial-time construction from a Muller automaton to automata for the open cover and meagre exception, together with a quadratic-size conversion from restricted Muller automata to Büchi automata.

If this is right

Every Muller-recognizable omega-language possesses an automatic Baire decomposition that is computable in polynomial time.
The open and meagre sets in the decomposition are themselves Muller-recognizable.
For the restricted class of Muller automata the decomposition sets are also Büchi-recognizable.
The Büchi automata have size at most quadratic in the size of the input Muller automaton.
The construction stays inside the class of finite automata without requiring higher-order devices.

Where Pith is reading between the lines

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

The algorithm could be used as a preprocessing step to simplify topological queries about regular omega-languages in verification tools.
Similar effective decompositions might exist for other topological notions such as automatic continuity or automatic measurability.
The quadratic conversion bound suggests that the restricted Muller class is close in expressive power to Büchi automata for this particular property.

Load-bearing premise

That every Muller-recognizable set admits an automatic Baire decomposition realized by automata, and that the topological simplicity of those sets always permits a quadratic-size conversion to Büchi automata.

What would settle it

Exhibit a concrete Muller automaton for which no polynomial-time constructible open and meagre automata exist that satisfy the automatic Baire property.

read the original abstract

A subset of a topological space possesses the Baire property if it can be covered by an open set up to a meagre set. For the Cantor space of infinite words Finkel introduced the automatic Baire category where both sets, the open and the meagre, can be chosen to be definable by finite automata. Here we show that, given a Muller automaton defining the original set, resulting open and meagre sets can be constructed in polynomial time. Since the constructed sets are of simple topological structure, it is possible to construct not only Muller automata defining them but also the simpler B\"uchi automata. To this end we give, for a restricted class of Muller automata, a conversion to equivalent B\"uchi automata of at most quadratic size.

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

Polynomial-time construction for automatic Baire witnesses from Muller automata, with quadratic Müller-to-Büchi conversion only for a restricted class.

read the letter

The main contribution is a polynomial-time algorithm that takes a Muller automaton and produces automata for the open set and the meagre set in the automatic Baire decomposition. It also gives a quadratic-size conversion from a restricted class of Muller automata to Büchi automata, relying on the simple topological structure of those constructed sets. This is new relative to Finkel's earlier definition; the explicit time bounds and the conversion size are the concrete advances. The work stays constructive and avoids any circular reductions or free parameters. The citation pattern is straightforward and appropriate for the subfield. The constructions look reproducible in principle once the details are checked. The restricted class for the Büchi step is the clearest soft spot. The stress-test note is on target: the polynomial-time part produces open and meagre sets, but the quadratic conversion applies only to the restricted class, so the paper must show that the output sets land inside that class or supply separate justification. If that link is missing or implicit, the Büchi claim weakens. The abstract gives no proof sketch or example, which makes the soundness hard to assess without the full text, but nothing in the stated claims suggests internal contradiction. This is narrow automata-theoretic work on infinite words and effective Baire category. Readers working on omega-automata, verification of topological properties, or descriptive set theory with automata will find the complexity results usable. It is worth a serious referee because the claims are algorithmic and can be checked or implemented directly. I would send it to peer review.

Referee Report

1 major / 0 minor

Summary. The paper claims that, given a Muller automaton recognizing a subset of the Cantor space, one can construct in polynomial time Muller automata for an open set and a meagre set witnessing the automatic Baire property. It further asserts that these constructed sets have simple topological structure, allowing not only Muller but also Büchi automata, and supplies a quadratic-size conversion from a restricted class of Muller automata to equivalent Büchi automata.

Significance. If the constructions hold, the result supplies an efficient, explicit algorithm for the automatic Baire property on Muller-recognizable sets together with a size-bounded conversion to the simpler Büchi model; the polynomial-time bound and the quadratic conversion are concrete strengths that would advance the study of automata-definable topological properties.

major comments (1)

[Section introducing the restricted Muller class and the conversion (likely §4 or §5)] The quadratic Büchi conversion is stated only for a restricted class of Muller automata. The manuscript must explicitly define the restrictions of this class (in the section introducing the conversion) and prove that the open and meagre sets output by the main polynomial-time construction belong to it; the appeal to 'simple topological structure' alone does not suffice to transfer the conversion result.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful review and positive assessment of the significance of our results. We address the single major comment below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

Referee: [Section introducing the restricted Muller class and the conversion (likely §4 or §5)] The quadratic Büchi conversion is stated only for a restricted class of Muller automata. The manuscript must explicitly define the restrictions of this class (in the section introducing the conversion) and prove that the open and meagre sets output by the main polynomial-time construction belong to it; the appeal to 'simple topological structure' alone does not suffice to transfer the conversion result.

Authors: We agree that the restrictions defining the class of Muller automata for which the quadratic-size Büchi conversion holds must be stated explicitly in the section introducing the conversion. We will revise the manuscript to include a precise definition of this restricted class. We will also add a dedicated proof (or subsection) showing that the open and meagre sets produced by the main polynomial-time construction satisfy the restrictions, thereby justifying the application of the conversion; the argument will make the 'simple topological structure' fully rigorous rather than relying on an informal appeal. revision: yes

Circularity Check

0 steps flagged

No circularity; direct constructive algorithm with independent conversion result.

full rationale

The paper presents an explicit polynomial-time construction of open and meagre sets from a given Muller automaton, followed by a separate quadratic-size conversion result that applies only to a restricted subclass of Muller automata. No derivation step reduces by definition, fitted parameter, or self-citation chain to its own inputs; the topological-simplicity claim is used only to motivate the separate conversion theorem, which is stated as an independent contribution. The derivation chain is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard automata-theoretic facts without introducing fitted parameters or new entities.

axioms (2)

standard math Muller automata define regular omega-languages and admit standard conversions under topological restrictions
Invoked implicitly when claiming polynomial construction and quadratic Büchi conversion.
domain assumption The automatic Baire property is well-defined for Muller-recognizable sets per Finkel's prior work
Background assumption enabling the algorithmic claim.

pith-pipeline@v0.9.0 · 5659 in / 1217 out tokens · 41072 ms · 2026-05-23T04:54:21.865602+00:00 · methodology

A polynomial-time algorithm for the automatic Baire property

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)