Logics for Reversible Regular Languages and Semigroups with Involution

Amaldev Manuel; Paul Gastin; R. Govind

arxiv: 1907.01214 · v1 · pith:LB7D3AG4new · submitted 2019-07-02 · 💻 cs.FL · cs.LO

Logics for Reversible Regular Languages and Semigroups with Involution

Paul Gastin , Amaldev Manuel , R. Govind This is my paper

Pith reviewed 2026-05-25 10:49 UTC · model grok-4.3

classification 💻 cs.FL cs.LO

keywords reversible regular languagesMSO logicFO logicsemigroups with involutionbetween predicateneighbour predicateregular language reversal

0 comments

The pith

MSO and FO logics with between and neighbour predicates characterize fragments of regular languages closed under reversal via semigroups with involution.

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

The paper shows how to extend monadic second-order and first-order logics with two new predicates to define classes of regular languages that stay the same when their words are reversed. It proves that the usual algebraic correspondences between these logics and varieties of finite semigroups continue to hold once the semigroups are equipped with an involution operation that models reversal. The extension works directly for MSO and for FO with the between predicate. For FO with the neighbour predicate the correspondence requires a set of extra equations on the involutive semigroups.

Core claim

We present MSO and FO logics with predicates `between' and `neighbour' that characterise various fragments of the class of regular languages that are closed under the reverse operation. The standard connections that exist between MSO and FO logics and varieties of finite semigroups extend to this setting with semigroups extended with an involution. The case is different for FO with neighbour relation where we show that one needs additional equations to characterise the class.

What carries the argument

MSO and FO logics extended by between and neighbour predicates, connected to varieties of finite semigroups equipped with an involution.

If this is right

Reversible regular languages admit uniform logical and algebraic descriptions through the added predicates and the involution.
Most fragments of the reversible class are captured exactly by the extended logics without further restrictions.
The neighbour predicate in FO requires supplementary equations on the involutive semigroup to achieve a complete match.
The same predicates suffice to separate the reversible languages from the full class of regular languages.

Where Pith is reading between the lines

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

The construction supplies a uniform method that could be applied to other closure properties such as complement or intersection.
Concrete finite semigroups with involution can now be checked directly against the extra equations to decide membership in the FO-neighbour fragment.
Automata constructions that respect the involution may be derived mechanically from the logical definitions.
The exception for the neighbour predicate suggests that neighbour-based logics are sensitive to the precise algebraic signature chosen for reversal.

Load-bearing premise

The usual logic-to-semigroup correspondences remain valid after an involution is added to the semigroups, except that the FO-neighbour case needs further equations.

What would settle it

A concrete reversible regular language that is definable in FO with the neighbour predicate yet fails to satisfy the additional equations, or a language satisfying those equations yet not definable in the logic.

read the original abstract

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 gives explicit MSO/FO characterizations of reversible regular languages via between and neighbour predicates and extends the semigroup correspondence to involutive semigroups, with one clear exception handled separately.

read the letter

The main takeaway is that the authors define MSO and FO logics using the predicates 'between' and 'neighbour' that pick out fragments of reverse-closed regular languages, then show the usual logic-to-semigroup links carry over once semigroups are equipped with an involution, except that the FO+neighbour case needs extra equations. That distinction is the concrete new piece; it does not collapse into prior results on reversible languages. The work stays inside the standard Eilenberg framework rather than building something from scratch, which keeps the contribution focused and easy to place. It states the results plainly in the abstract and flags the exception without trying to force a uniform statement. The algebraic extension looks like a direct but non-trivial lift of the existing correspondences, and naming the extra equations for the neighbour case is useful because it shows where the lift stops being automatic. The only soft spot visible from the abstract is the lack of any proof outline or small example, so the characterizations have to be taken on the strength of the full derivations; if those are present and check out, the claim holds. No circular definitions or self-referential fitting appear. This is for people already working on algebraic automata theory or reversible languages; it will not move anything outside that niche. It is worth sending to peer review so the technical details can be checked by specialists who know the involution setup.

Referee Report

0 major / 2 minor

Summary. The paper introduces MSO and FO logics augmented with 'between' and 'neighbour' predicates that characterize fragments of regular languages closed under reversal. It extends the classical Eilenberg correspondences between these logics and varieties of finite semigroups to the setting of semigroups equipped with an involution, with the exception that FO logic with the neighbour predicate requires additional equations to fully characterize the corresponding class.

Significance. If the characterizations and extensions hold, the work supplies a uniform logical and algebraic framework for reversible regular languages, generalizing standard results on MSO/FO definability and semigroup varieties to the involution setting. The explicit identification of the FO-neighbour exception provides a precise boundary on where the standard correspondences fail to lift directly.

minor comments (2)

The abstract states the main results but the manuscript should include a brief proof sketch or reference to the key theorem establishing the extension of the MSO/FO correspondences to involutive semigroups (e.g., the theorem corresponding to the second sentence of the abstract).
Notation for the involution operation on semigroups should be introduced explicitly in the preliminaries section and used consistently when stating the additional equations for the FO-neighbour case.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive recommendation to accept the manuscript. The provided summary correctly reflects the scope and main results of the paper.

Circularity Check

0 steps flagged

No significant circularity; derivation extends external standard results

full rationale

The paper's central claims rest on extending known Eilenberg-style correspondences between MSO/FO logics and semigroup varieties to the involution setting, with explicit predicates (between, neighbour) and an acknowledged exception for FO+neighbour requiring extra equations. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the abstract or claim structure. The work treats the standard connections as independent external facts and derives the reversible-language characterizations from them without reducing the target results to definitions or fits internal to the paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no concrete free parameters, axioms, or invented entities; the work rests on standard background results in logic and semigroup theory whose details are not visible here.

pith-pipeline@v0.9.0 · 5596 in / 1185 out tokens · 29582 ms · 2026-05-25T10:49:38.369509+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat recovery; no involution or language-theoretic predicates unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We present MSO and FO logics with predicates ‘between’ and ‘neighbour’ that characterise various fragments of the class of regular languages that are closed under the reverse operation. … The standard connections … extend to this setting with semigroups extended with an involution.
IndisputableMonolith/Foundation/LogicAsFunctionalEquation.lean SatisfiesLawsOfLogic; Translation Theorem unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 15. The syntactic ⋆-semigroup … satisfies exe⋆ = ex⋆e⋆ …

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.