{"id":"c3d40bdf-1622-431b-9e6b-c8dc040fabeb","arxiv_id":"2506.05824","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Positive varieties of regular lattice languages are in bijection with pseudo-varieties of finite ordered monoids, generalizing Pin's positive variety theorem.","lead":"Lattice-valued languages assign a lattice element, not just yes or no, to each word. This paper proves a bijection between closed classes of such languages and pseudo-varieties of ordered monoids, extending Pin's theorem and sketching applications to Markov chains.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4 lacks a nonemptiness hypothesis: the empty positive variety maps to all constant languages, so the stated bijection fails as written.","rationale":"The reader's stated weakest assumption, namely that Corollary 1 transfers Pin's Proposition 7 to arbitrary lattices relies on the syntactic monoid of a B-language viewed as a Λ-language being the same as the ordinary one. This transfer is actually sound: for a B-language, values are only 0 and 1, and the paper's syntactic preorder w1⪯w2 iff ∀u,v: L(uw1v)≤L(uw2v) reduces to the ordinary positive syntactic order (xw2y∈L ⇒ xw1y∈L) because 0<1 in Λ. Hence the syntactic ordered monoid is unchanged, and Corollary 1 is a legitimate one-line transfer. The more concrete gap in the central theorem is the missing nonemptiness assumption. The definitions in Section 3 do not require positive varieties to be nonempty, and the proof of Lemma 2 uses a member of L to generate constant languages via Λ-morphisms; this fails when L is empty. Under the standard convention that pseudo-varieties contain the trivial monoid via closure under the empty finite product, the empty positive variety maps to the class of all constant Λ-languages, so Theorem 4 is false as stated. This is a real correctness issue, though easily repaired by adding a nonempty hypothesis. The reader's CONDITIONAL verdict remains appropriate because of the additional application-section errors; our concern does not change the verdict category.","tokens_in":13037,"tokens_out":34737,"duration_ms":329199,"concrete_test":"Verify the empty case: fix any complete lattice Λ, take L=∅, and compute V(L) and V(V(L)) under the definitions in Section 3.3. If V(L) is taken to be the trivial pseudo-variety, exhibit cons(1) (or any constant) as a Λ-language recognized by the trivial ordered monoid and show it lies in V(V(∅)) but not in ∅, contradicting Theorem 4. If one instead adopts the convention that the empty class is a pseudo-variety, then re-examine the phrase 'smallest variety' and the closure under the empty product; either way, the statement of Theorem 4 needs an explicit nonemptiness assumption on positive varieties (and on pseudo-varieties) before it is true as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper defines a positive variety as a class of regular Λ-languages closed under joins, meets, quotients, inverse homomorphisms, and Λ-morphisms (Section 3), with no nonemptiness requirement. The empty class ∅ satisfies these closure conditions vacuously. In Theorem 4, for such L, V(L) is defined as the smallest variety containing the syntactic monoids of languages in L, i.e., the pseudo-variety generated by no monoids. Under the standard convention that a pseudo-variety is closed under finite direct products and hence contains the trivial ordered monoid (the empty product), V(∅) is the trivial pseudo-variety. Then V(V(∅)) is exactly the class of all Λ-languages recognized by the trivial monoid, which are the constant Λ-languages on all finite alphabets. This is not equal to ∅, so V∘V(L)=L fails. The proof also implicitly needs a base language in L to manufacture constant languages via Λ-morphisms; for instance, in Lemma 2 the term cons(P(m)) is assumed to lie in L, which has no justification when L is empty. The fix is to require positive varieties to be nonempty, or to require them to contain the constant languages, and correspondingly to require pseudo-varieties to be nonempty.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13306,"tokens_out":18117,"duration_ms":205697,"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":[{"comment":"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.","section":"Section 3 (definition of positive variety) and Theorem 4"},{"comment":"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.","section":"Lemma 2"},{"comment":"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.","section":"Corollary 1"}],"minor_comments":[{"comment":"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":"Lemma 1"},{"comment":"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.","section":"Section 2 and Proposition 6"},{"comment":"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.","section":"Theorem 5"},{"comment":"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":"Proposition 8"},{"comment":"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":"Section 4"},{"comment":"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.","section":"Section 3, definition of positive variety"}],"recommendation":"major_revision","confidential_remarks":"The central theorem is plausible and the proof strategy is sound, but the empty-variety edge case and the gaps in Lemma 2 and Corollary 1 need to be addressed before the result can be accepted. The Markov-chain section is too informal to evaluate and should be clearly labeled as speculative. I recommend major revision rather than rejection, since the issues appear fixable within the scope of the manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nWhere 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.\n\nThe 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.\n\nThe 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.\n\nMinor 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.\n\nOverall: 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.","headline":"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.","tokens_in":13807,"tokens_out":6670,"would_cite":false,"duration_ms":63186,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q45","20M07","20M35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Lattice-valued languages match ordered monoids one-to-one.","keywords":["lattice languages","positive varieties","ordered monoids","Eilenberg's variety theorem","syntactic monoids","order-preserving colorings","shuffle ideals","Markov chains"],"falsifier":"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.","tokens_in":12847,"feed_emoji":"🔤","tokens_out":11258,"duration_ms":114113,"temperature":0.7,"pith_summary":"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.","feed_headline":"Beyond yes/no: lattice languages meet ordered monoids","feed_subtitle":"Positive varieties of regular lattice languages correspond exactly to pseudo-varieties of finite ordered monoids.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the original positive variety theorem and the key external result (Proposition 5.3, quoted as Proposition 7) that the surjectivity direction of the correspondence relies on.","marker":"[12]"},{"why":"The classical Eilenberg variety theorem that this paper generalizes from Boolean languages to lattice-valued languages.","marker":"[7]"},{"why":"Introduces multi-valued and lattice-valued languages as an object of study, giving the motivation and examples for the lattice-language setting.","marker":"[4]"},{"why":"Defines lattice automata and recognition by lattice languages, establishing the model of computation that the paper works with.","marker":"[11]"}],"fun_headline_variants":["Lattice languages get their own positive variety theorem","Positive varieties: lattice languages and ordered monoids align","Correspondence theorem for lattice language varieties","From yes/no to lattices: variety theorem proved"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Lattice languages get their own positive variety theorem","Positive varieties: lattice languages and ordered monoids align","Correspondence theorem for lattice language varieties","From yes/no to lattices: variety theorem proved"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000807,"raw_usage":{"total_tokens":3507,"prompt_tokens":873,"completion_tokens":2634,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":489,"completion_tokens_details":{"reasoning_tokens":2574}},"tokens_in":489,"tokens_out":2634,"duration_ms":24253,"temperature":1.0,"reasoning_tokens":2574,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:15:37.854964+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A variety theorem without complementation.Russian Mathematics (Izvestija vuzov","cited_arxiv_id":null,"evidence_quote":"Supplies the original positive variety theorem and the key external result (Proposition 5.3, quoted as Proposition 7) that the surjectivity direction of the correspondence relies on."},{"cited_title":"Academic press, 1974","cited_arxiv_id":null,"evidence_quote":"The classical Eilenberg variety theorem that this paper generalizes from Boolean languages to lattice-valued languages."},{"cited_title":"Model checking with multi-valued logics","cited_arxiv_id":null,"evidence_quote":"Introduces multi-valued and lattice-valued languages as an object of study, giving the motivation and examples for the lattice-language setting."},{"cited_title":"Lattice automata","cited_arxiv_id":null,"evidence_quote":"Defines lattice automata and recognition by lattice languages, establishing the model of computation that the paper works with."}],"review_version":1}