Positive Varieties of Lattice Languages

Yuji Komatsu; Yusuke Inoue

REVIEW 3 major objections 6 minor 18 references

Positive Varieties of Lattice Languages

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Lattice-valued languages match ordered monoids one-to-one.

desk verdict A mostly sound extension of Pin's variety theorem to lattice languages, with a real edge-case gap in Theorem 4 and an overreaching Markov chain application. read the letter →

arxiv 2506.05824 v1 pith:LTQBUQ7B submitted 2025-06-06 cs.FL

Yusuke Inoue , Yuji Komatsu This is my paper

classification cs.FL MSC 68Q4520M0720M35

keywords latticelanguagespositivevarietiesorderedmonoidsEilenberg'svarietytheoremsyntacticorder-preservingcoloringsshuffleidealsMarkovchains

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper claims that the algebraic theory of regular languages survives a change of semantics: instead of assigning each word a yes/no answer, one may assign it an element of any complete lattice, and the same varietal correspondence still holds. Concretely, it proves a one-to-one correspondence between positive varieties of regular lattice languages and pseudo-varieties of finite ordered monoids, extending Pin's positive variety theorem to lattice-valued languages. The proof requires one extra closure condition — invariance under lattice-endomorphisms ($\Lambda$-morphisms) — which the authors show is necessary to prevent the same monoid class from being paired with many different language classes. If the theorem is right, standard algebraic tools for ordered monoids become directly applicable to lattice-valued automata and to problems such as the Markov-chain examples sketched in the paper.

What carries the argument

The load-bearing objects are order-preserving colorings (op-colorings), monotone maps $P\colon M\to\Lambda$ from an ordered monoid to a complete lattice, which generalize the order ideals of Pin's proof. Their work is organized around the ideal colorings $\iota[m]$, defined by $\iota[m](x)=0$ if $x\le m$ and $\iota[m](x)=1$ otherwise, together with the representation identity $P = \bigwedge_{m\in M}(\iota[m]\vee \mathrm{cons}(P(m)))$ (Proposition 6), which expresses an arbitrary op-coloring as a meet of simple colorings built from ideal colorings and constants. Lemma 1 then shows that each ideal coloring of the syntactic ordered monoid of a regular $\Lambda$-language $L$ can be constructed from $L$ by the operations allowed in a positive variety, which is the step that makes the two directions of the correspondence close.

What would settle it

Use the three-element chain $\Lambda=\{0<1<2\}$ and take a finite ordered monoid $M$ with a non-trivial order for which Pin's Proposition 5.3 produces ordinary languages. Reinterpret those languages as $\Lambda$-languages by sending accepted words to 0 and rejected words to 1, and compute their syntactic ordered monoids. If at least one of these syntactic monoids is strictly smaller than the ordinary one, so that $M$ no longer embeds into their product, then Corollary 1 fails and the surjectivity half of Theorem 4 collapses.

Watch

Extended reading notes

Core claim

The paper proves Theorem 4, the Variety Theorem for lattice languages: for every complete lattice $\Lambda$, the map $V$ sending a positive variety $L$ of regular $\Lambda$-languages to the smallest pseudo-variety of finite ordered monoids generated by the syntactic ordered monoids of languages in $L$, and the map $V$ sending a pseudo-variety $M$ of finite ordered monoids to the class of all $\Lambda$-languages recognized by members of $M$, are mutual inverses. In the paper's own terms, $V\circ V(L)=L$ and $V\circ V(M)=M$. The extension of Pin's theorem requires replacing order ideals by order-preserving colorings $P\colon M\to\Lambda$, and closing positive varieties under $\Lambda$-morphisms; without this closure, classes such as the constant languages over a three-element lattice collapse many-to-one onto the same trivial pseudo-variety. The theorem is proved by showing that ideal colorings of syntactic monoids can be reconstructed from the language using joins, meets, quotients, and $\Lambda$-morphisms.

Load-bearing premise

The correspondence can fail if the ordered monoid that recognizes a language changes when the language is reinterpreted as taking values in a larger lattice; the paper relies on this invariance for ordinary two-valued languages without giving a full proof.

Editorial extensions

If this is right

Every pseudo-variety of finite ordered monoids — aperiodic monoids, groups, and so on — now names a canonical class of lattice languages, and membership in that class is decidable whenever membership in the pseudo-variety is.
Classical language-theoretic results expressed through ordered monoids, such as the characterization of shuffle ideals as exactly the languages recognized by monoids whose identity is the greatest element, extend to any finite lattice.
For the Markov-chain application, the language describing which ergodic class a word reaches is a shuffle ideal, so its syntactic ordered monoid is aperiodic; this gives an algebraic invariant for reducible Markov chains.
Because pseudo-varieties do not depend on the choice of lattice, the theorem implies a one-to-one correspondence between the positive varieties over any two complete lattices, which the authors suggest could lead to a global, lattice-independent variety theorem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: the correspondence invites a lattice-valued counterpart of identity-based classification — for a pseudo-variety defined by identities of ordered monoids, one can ask which lattice languages belong to it, a translation the paper leaves unexplored.
The Markov-chain discussion could be pushed toward quantitative statements: assigning lattice values that encode transition probabilities would make the syntactic ordered monoid carry information about mixing times, potentially touching the cutoff phenomenon the authors mention.
One natural next step is a careful verification, on small non-Boolean lattices, of the transfer from ordinary languages to $\Lambda$-languages on which the surjectivity half of the theorem rests; the authors assert this transfer as Corollary 1 without a full proof.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version: the paper proves a natural extension of Pin's positive variety theorem to lattice-valued languages. The key idea—replacing Pin's order ideals with order-preserving colorings, and closing positive varieties under Λ-morphisms—is the right generalization, and the proof of the main theorem is coherent. But as written, Theorem 4 is false for the empty positive variety, and the Markov chain application contains a claim about shuffle ideals that doesn't hold in general.

What's genuinely new: the bijection between positive varieties of regular Λ-languages and pseudo-varieties of finite ordered monoids, for arbitrary complete lattices Λ. That's not in Pin's paper or anywhere else I know. The proof follows Pin's strategy but needs real adjustments: Lemma 1's construction of ideal colorings via threshold Λ-morphisms is the technical heart, and Lemma 2 correctly shows that the Λ-morphism closure is what makes the correspondence bijective. For nonempty varieties, the theorem holds up. The shuffle ideal characterization (Proposition 8) is a clean extension of Pin's Theorem 6.4.

Where it's soft: the empty case. The definition of positive variety doesn't require nonemptiness, so the empty class is a positive variety. V(∅) should be the smallest pseudo-variety. Under the standard convention that pseudo-varieties contain the trivial monoid, V(∅) is the trivial pseudo-variety, and applying V gives all constant languages—not ∅. Lemma 2 silently assumes you have a language in L to build constants. The fix is trivial: require positive varieties to be nonempty, or to contain the constant languages. But the theorem as stated needs that hypothesis.

The surjectivity direction, which the reader worried about, seems fine: Corollary 1's transfer from B-languages to Λ-languages is harmless because the syntactic monoid construction only depends on the preorder, and for B-languages it gives the ordinary one.

The Markov chain section is shakier. The claim that any language encoding the ergodic-class problem is a shuffle ideal is false. A superword of a word that reaches one ergodic class can reach a different one, giving incomparable lattice values. The example works because of the specific automaton, but the general statement doesn't. This doesn't touch the main theorem, but the application should be corrected.

Minor issues: in Lemma 1, w,w' are typed as elements of M_L instead of Σ*; and the sentence about L^{-1}({i}) for i∈{0,1} should presumably be {1,2}. These are obvious typos.

Overall: the central result is a solid contribution to algebraic automata theory, with proofs that mostly work. It deserves a serious referee; the referee should ask for the nonemptiness fix and a correction to the application section. I'd be comfortable citing the main theorem after those changes.

Referee Report

3 major / 6 minor

Summary. The paper studies lattice-valued languages over a complete lattice Λ, recognized by finite ordered monoids via order-preserving colorings. It defines positive varieties of regular Λ-languages as classes closed under joins, meets, quotients, inverse homomorphisms, and Λ-morphisms, and pseudo-varieties of finite ordered monoids as classes closed under divisors and finite direct products. The main result (Theorem 4) asserts a bijection between these two classes, extending Pin's positive variety theorem to lattice languages. The proof proceeds through syntactic ordered monoids, ideal colorings, Lemma 1 (representing ideal colorings of the syntactic monoid from a given language), Lemma 2 (closure under recognition by products of syntactic monoids), and an external result of Pin (Proposition 7 / Proposition 5.3 in [12]) for the surjectivity direction. A final section sketches applications to shuffle ideals and to finite-state Markov chains.

Significance. If correct, the main theorem gives a natural Eilenberg-type correspondence for lattice-valued languages and is a genuine generalization of Pin's theorem; order-preserving colorings are a reasonable analogue of order ideals, and the proof is not circular. The paper is clearly written and the main line of argument is plausible. However, as stated the theorem has an edge-case flaw concerning the empty positive variety, and the proof of Lemma 2 contains a gap about constant languages. These issues are fixable but currently prevent the central claim from being accepted as stated. No machine-checked proofs or code are provided, and the Markov-chain section is explicitly only an outline.

major comments (3)

[Section 3 (definition of positive variety) and Theorem 4] The empty class ∅ satisfies the closure conditions in the definition of positive variety vacuously, so it is a positive variety under the definition as written. If pseudo-varieties are taken to be closed under finite direct products and hence to contain the trivial ordered monoid (the empty product), then V(∅) is the trivial pseudo-variety and V(V(∅)) is the class of all constant Λ-languages on all finite alphabets, which is not ∅. Thus the bijection in Theorem 4 fails as stated for L=∅. The proof of Lemma 2 also needs a language already in L to manufacture the constant factors via Λ-morphisms, which is impossible when L=∅. Please add a nonemptiness hypothesis on positive varieties (and correspondingly on pseudo-varieties), or state explicitly the convention on empty products and adjust the argument accordingly.
[Lemma 2] In the proof of Lemma 2, after writing L=∧_{m∈M}(ι[m]∘η ∨ cons(P(m))), the text says 'Note that every constant mapping is a Λ-morphism' and then concludes that L is represented using meets, joins, and Λ-morphisms of the languages ι[m_i]∘π_i∘η. This skips the essential step that each constant language cons(P(m)) must itself be shown to belong to the positive variety L. A constant language arises only by composing a constant Λ-morphism with some language already in L and then applying an inverse homomorphism to change the alphabet; this construction is not given and cannot be carried out when L=∅. Please supply the explicit construction and state the needed nonemptiness assumption.
[Corollary 1] Corollary 1 is the load-bearing step for the surjectivity direction V∘V(M)=M in Theorem 4, but it is justified only by the sentence 'a B-language can be considered as a Λ-language.' One must verify that the syntactic ordered monoid of a {0,1}-valued language is the same whether the order is computed in B or in the ambient complete lattice Λ, and that the languages supplied by Pin's Proposition 7 remain in the Λ-version of V(M). This verification is straightforward but should be written out, since the entire surjectivity argument depends on it.

minor comments (6)

[Lemma 1] In the proof of Lemma 1, 'there are words w,w′∈M_L' should be 'there are elements u,u′∈M_L' or 'words w,w′∈Σ*'; later the expression w\L/w′ uses words, so the notation should be made consistent.
[Section 2 and Proposition 6] The notation cons(λ) is introduced as a mapping Λ→Λ, but in Proposition 6 and Lemma 2 it is used as a constant op-coloring on an ordered monoid or as a constant Λ-language. Please disambiguate these overloaded uses.
[Theorem 5] In the proof of Theorem 5, 'P_λ(x)' should be 'P_λ(x_λ)', and the constant term written 'cons(λ)' inside the definition of P should be explicitly the element λ rather than a function on the index set.
[Proposition 8] In the proof of Proposition 8, the line 'by 1_M ≥ v_i for each 0≤i≤n' compares a word v_i with an element of an ordered monoid; it should read '1_M ≥ η(v_i)' or 'η(v_i) ≤ 1_M'.
[Section 4] The text writes 'L^{-1}({i}) ... for each i∈{0,1}', but the lattice Λ=P({1,2}) has atoms {1} and {2}, so the index set should be {1,2}. Also, the phrase 'probability of the language' is used without a definition; please clarify.
[Section 3, definition of positive variety] The paper should state explicitly that joins and meets in the definition of positive variety are finite joins and meets; otherwise arbitrary joins or meets of regular languages need not be regular, and Theorem 1 only establishes closure under binary operations.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof imports Pin's external lemmas and proves the lattice generalization by construction, not by assuming the conclusion.

full rationale

The derivation chain is self-contained relative to Pin's positive variety theorem. Theorem 4 has two directions. The inclusion V(V(L)) subset of L is proved by Lemma 2, which uses Lemma 1 to construct every ideal coloring of a product of syntactic monoids from the original languages via joins, meets, quotients, and Lambda-morphisms; this is a direct construction, not a restatement of the theorem. The inclusion M subset of V(V(M)) is imported from Pin's Proposition 5.3 through Corollary 1; this is an external result, not a self-citation, and the transfer to Lambda-languages is justified because B-valued languages are also Lambda-valued languages. The definitional addition of closure under Lambda-morphisms is motivated by a concrete counterexample (Cons versus B) and is used to make the correspondence bijective; it does not presuppose the correspondence itself. No fitted parameters are renamed as predictions, and no uniqueness theorem is imported from the present authors. The only caveat visible in the manuscript is the absence of a nonemptiness condition in the definitions of positive variety and pseudo-variety, which may affect the truth of the theorem for the empty class; that is a correctness concern, not a circularity concern.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

No fitted or hand-chosen numeric parameters. The theorem relies on two propositions and one theorem from Pin [12] as external black boxes, plus standard lattice theory. One new mathematical object, op-colorings, is introduced; it is a direct generalization of Pin's order ideals and is load-bearing only through the proofs that use it.

assumptions (4)

domain assumption Proposition 7 (Pin [12], Prop 5.3): each ordered monoid in a pseudo-variety is a submonoid of a product of syntactic monoids of ordinary languages in the corresponding positive variety.
Used without proof in §3.3 to prove Corollary 1 and the V∘V(M)=M direction of Theorem 4.
domain assumption Proposition 2 (Pin [12], Cor 2.6): a morphism from the free monoid can be lifted through a surjective morphism of ordered monoids.
Used in Lemma 2 to pull back ideal-coloring languages under ψ.
domain assumption Theorem 6.4 (Pin [12]): shuffle ideals are exactly languages recognized by ordered monoids whose identity is the greatest element.
Used only in Proposition 8 for the Markov chain application; if false, the application weakens but the main theorem stands.
standard math Standard lattice and order theory: complete lattices have top and bottom, pointwise joins/meets are order-preserving, and the syntactic construction produces a monoid congruence.
Throughout Sections 2 and 3; the congruence claim is asserted without proof but is straightforward.

invented entities (1)

Order-preserving colorings (op-colorings)
purpose: Replace order ideals with lattice-valued maps so that lattice languages can be recognized by ordered monoids.
Introduced in §2.2 as the key technical device. It is a mathematical definition, not an empirical entity; it has no falsifiable handle outside the paper, but it is used explicitly in the proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Positive Varieties of Lattice Languages." pith.science (2026). https://pith.science/paper/LTQBUQ7B

@misc{pith2026250605824,
  author       = {Pith},
  title        = {Pith review of: Positive Varieties of Lattice Languages},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LTQBUQ7B}},
  note         = {Machine review of arXiv:2506.05824}
}

read the original abstract

While a language assigns a value of either `yes' or `no' to each word, a lattice language assigns an element of a given lattice to each word. An advantage of lattice languages is that joins and meets of languages can be defined as generalizations of unions and intersections. This fact also allows for the definition of positive varieties -- classes closed under joins, meets, quotients, and inverse homomorphisms -- of lattice languages. In this paper, we extend Pin's positive variety theorem, proving a one-to-one correspondence between positive varieties of regular lattice languages and pseudo-varieties of finite ordered monoids. Additionally, we briefly explore algebraic approaches to finite-state Markov chains as an application of our framework.

Figures

Figures reproduced from arXiv: 2506.05824 by the authors.

**Figure 1.** Markov chain C. A Markov chain with a state space Ω is irreducible if Ω itself is ergodic. Because ergodic classes are convenient for analyzing Markov chains, reducible [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗

**Figure 2.** DFA A simulating C. In this context, it is natural to ask the problem of ergodic classes: Which ergodic class does each word reach? To consider this, let us use lattice languages. First, let Λ = P({1, 2}) be the lattice of the powerset of {1, 2}. That is, ∅ = 0 is the least element, {1, 2} = 1 is the greatest element, and {1} and {2} are incomparable. Next, let F : Ω → Λ be the coloring on the DFA A defined as F(s) … view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[12]

A variety theorem without complementation.Russian Mathematics (Izvestija vuzov

Jean- ´Eric Pin. A variety theorem without complementation.Russian Mathematics (Izvestija vuzov. Matematika), 39:80–90, 1995

work page 1995
[1]

Shuffling cards and stopping times.The Amer- ican Mathematical Monthly, 93(5):333–348, 1986

David Aldous and Persi Diaconis. Shuffling cards and stopping times.The Amer- ican Mathematical Monthly, 93(5):333–348, 1986

work page 1986
[2]

Markov chains and unambiguous automata.Journal of Computer and System Sciences, 136:113–134, 2023

Christel Baier, Stefan Kiefer, Joachim Klein, David M¨ uller, and James Worrell. Markov chains and unambiguous automata.Journal of Computer and System Sciences, 136:113–134, 2023

work page 2023
[3]

Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited.Forum Mathematicum, 26(6):1737–1761, 2014

Adolfo Ballester-Bolinches, Jean ´Eric Pin, and Xaro Soler-Escriv` a. Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited.Forum Mathematicum, 26(6):1737–1761, 2014

work page 2014
[4]

Model checking with multi-valued logics

Glenn Bruns and Patrice Godefroid. Model checking with multi-valued logics. InInternational Colloquium on Automata, Languages, and Programming, pages 281–293. Springer, 2004

work page 2004
[5]

Generating a random permutation with random transpositions.Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und verwandte Gebiete, 57(2):159–179, 1981

Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions.Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und verwandte Gebiete, 57(2):159–179, 1981

work page 1981
[6]

Springer Science & Business Media, 2009

Manfred Droste, Werner Kuich, and Heiko Vogler.Handbook of weighted automata. Springer Science & Business Media, 2009

work page 2009
[7]

Academic press, 1974

Samuel Eilenberg.Automata, languages, and machines. Academic press, 1974

work page 1974

Show all 18 references

[8]

Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations.Journal of the ACM (JACM), 56(1):1–66, 2009

Kousha Etessami and Mihalis Yannakakis. Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations.Journal of the ACM (JACM), 56(1):1–66, 2009

2009
[9]

Semidirect product decomposi- tions for periodic regular languages

Yusuke Inoue, Kenji Hashimoto, and Hiroyuki Seki. Semidirect product decomposi- tions for periodic regular languages. InInternational Conference on Developments in Language Theory, pages 173–188. Springer, 2024

2024
[10]

Van Nostrand, 1960

John G Kemeny and James Laurie Snell.Finite Markov Chains. Van Nostrand, 1960

1960
[11]

Lattice automata

Orna Kupferman and Yoad Lustig. Lattice automata. InInternational Work- shop on Verification, Model Checking, and Abstract Interpretation, pages 199–213. Springer, 2007

2007
[13]

Mathematical foundations of automata theory.Lecture notes LI- AF A, Universit´ e Paris, 7:73, 2010

Jean- ´Eric Pin. Mathematical foundations of automata theory.Lecture notes LI- AF A, Universit´ e Paris, 7:73, 2010

2010
[14]

Syntactic semiring of a language

Libor Pol´ ak. Syntactic semiring of a language. InInternational Symposium on Mathematical Foundations of Computer Science, pages 611–620. Springer, 2001

2001
[15]

Unified theory for finite markov chains.Advances in Mathematics, 347:739–779, 2019

John Rhodes and Anne Schilling. Unified theory for finite markov chains.Advances in Mathematics, 347:739–779, 2019

2019
[16]

Random walks on finite groups

Laurent Saloff-Coste. Random walks on finite groups. InProbability on discrete structures, pages 263–346. Springer, 2004

2004
[17]

Springer Science & Business Media, 2012

Arto Salomaa and Matti Soittola.Automata-theoretic aspects of formal power series. Springer Science & Business Media, 2012

2012
[18]

On finite monoids having only trivial subgroups.Inf

Marcel Paul Sch¨ utzenberger. On finite monoids having only trivial subgroups.Inf. Control., 8(2):190–194, 1965

1965

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [12]

A variety theorem without complementation.Russian Mathematics (Izvestija vuzov

Jean- ´Eric Pin. A variety theorem without complementation.Russian Mathematics (Izvestija vuzov. Matematika), 39:80–90, 1995

work page 1995

[2] [1]

Shuffling cards and stopping times.The Amer- ican Mathematical Monthly, 93(5):333–348, 1986

David Aldous and Persi Diaconis. Shuffling cards and stopping times.The Amer- ican Mathematical Monthly, 93(5):333–348, 1986

work page 1986

[3] [2]

Markov chains and unambiguous automata.Journal of Computer and System Sciences, 136:113–134, 2023

Christel Baier, Stefan Kiefer, Joachim Klein, David M¨ uller, and James Worrell. Markov chains and unambiguous automata.Journal of Computer and System Sciences, 136:113–134, 2023

work page 2023

[4] [3]

Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited.Forum Mathematicum, 26(6):1737–1761, 2014

Adolfo Ballester-Bolinches, Jean ´Eric Pin, and Xaro Soler-Escriv` a. Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited.Forum Mathematicum, 26(6):1737–1761, 2014

work page 2014

[5] [4]

Model checking with multi-valued logics

Glenn Bruns and Patrice Godefroid. Model checking with multi-valued logics. InInternational Colloquium on Automata, Languages, and Programming, pages 281–293. Springer, 2004

work page 2004

[6] [5]

Generating a random permutation with random transpositions.Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und verwandte Gebiete, 57(2):159–179, 1981

Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions.Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und verwandte Gebiete, 57(2):159–179, 1981

work page 1981

[7] [6]

Springer Science & Business Media, 2009

Manfred Droste, Werner Kuich, and Heiko Vogler.Handbook of weighted automata. Springer Science & Business Media, 2009

work page 2009

[8] [7]

Academic press, 1974

Samuel Eilenberg.Automata, languages, and machines. Academic press, 1974

work page 1974