{"id":"08f75b73-792d-43d7-a12a-58f352526ce3","arxiv_id":"2411.15338","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Semi-conditional matrix grammars with as few as three nonterminals, or with small degrees and short matrices, are computationally complete for the class of recursively enumerable languages.","lead":"The paper proves that several resource-limited families of semi-conditional matrix grammars can generate all recursively enumerable languages, improving known bounds on nonterminals and matrix length for these grammars. The results map part of the Pareto frontier for a classic regulated rewriting formalism, which matters for understanding the trade-offs between grammar size and generative power.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 9's failure-case simulation has an off-by-one error: mφ,1 transforms C^{k+1} into C^{k+g}, not C^{k+1+g}, so the modular uniqueness argument fails and the reverse inclusion is unproved as written.","rationale":"The reader's weakest assumption was that the reverse-inclusion proofs depend on structural invariants of the normal forms and on the cited two-nonterminal graph-controlled grammar result from [6, Thm. 4]. The normal-form invariants in §3 are stated without full proof but appear correct and are checkable from the morphisms given there. The genuinely load-bearing defect I find is internal to Theorem 9: the failure-case matrices do not satisfy the modular equation claimed in the proof, because of an off-by-one error in the number of C's. This is not an objection to the plausibility of the overall result—the construction is likely fixable—but it means the proof of SSCM(0,*;3;*,*) = RE, one of the paper's headline claims, is incomplete as written. This reinforces the reader's CONDITIONAL verdict rather than changing it.","tokens_in":22331,"tokens_out":21640,"duration_ms":182803,"concrete_test":"Recompute the C-count: instantiate v=2, ℓ=1, g(ℓ)=2, and start from state 2, i.e., w=C^3u with Y_1 absent. Apply mφ,1_1: C^3u → C^2u → C^1·C^3u = C^4u. Then mφ,2_1 requires exactly 1+2+1=4 occurrences of C and fires, producing C^{f+1}u from state 2 even though the matrix belongs to rule 1. This contradicts the paper's claim that the construction enforces k=ℓ=ℓ′; either the count equation or the matrices must be corrected.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Theorem 9 (SSCM(0,*;3;*,*) = RE), the failure-case simulation has an off-by-one error. Matrix mφ,1_ℓ = [(C→λ, C→C^{g(ℓ)+1}), ∅, Y_ℓ] applied to w = C^{k+1}u yields C^{k+g(ℓ)}u, not C^{(k+1)+g(ℓ)}u as stated: one C is deleted, then one C is replaced by C^{g+1}, giving a net change of g−1. Matrix mφ,2_ℓ'→f contains ℓ'+g(ℓ') copies of C→λ followed by C→C^{f+1}; to apply it, the current string must have exactly ℓ'+g(ℓ')+1 occurrences of C (the deletions must leave one C for the final rule), not ℓ'+g(ℓ') as claimed. Matching the actual post-mφ,1 count k+g(ℓ) with this requirement gives k+vℓ = ℓ'(v+1)+1, i.e., k ≡ ℓ+1 (mod v+1). Hence k=ℓ+1, ℓ'=ℓ is a solution: the failure matrices for rule ℓ can fire at state ℓ+1 whenever Y_ℓ is absent, following a red edge that belongs to vertex ℓ, not to the current vertex ℓ+1. This breaks the central invariant of the reverse inclusion. The intended modular check only works if the exponent in C→C^{g(ℓ)+1} is raised by one (or g is redefined), so the result may be repairable, but the proof as written is incorrect.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies resource-bounded semi-conditional matrix grammars, parameterized by the degree (i,j), the number of nonterminals, the number of conditional matrices, the maximum matrix length, and the number of non-simple matrices. It claims RE-completeness for several new grammar families, including SSCM(2,1;5;3,2), SSCM(3,1;5;2,2), SSCM(3,1;4;3,3), several SCM classes with four nonterminals and binary matrices, and SCM classes with three nonterminals. The proofs simulate Geffert-type normal forms, the Masopust-Meduna normal form, and, for Theorem 9, a two-nonterminal graph-controlled grammar from the literature.","tokens_in":22677,"tokens_out":12092,"duration_ms":121694,"significance":"If the theorems are correct, the results form a substantial advance in the descriptional complexity of regulated rewriting: the known SSCM bound is improved from seven nonterminals to five, the first degree-(2,1) SSCM completeness result is obtained, and several trade-offs with four or three nonterminals are established. The constructions are explicit and the resource counts are stated precisely, which is a genuine strength. However, the proof of Theorem 9 contains a load-bearing arithmetic error in the failure-case simulation, and several reverse-inclusion proofs are delegated to informal inductions; the claimed equalities are therefore not all established in the present version.","major_comments":[{"comment":"The reverse-inclusion proof of Theorem 9 contains an off-by-one error in the failure-case simulation. The paper states that applying mφ,1_ℓ to w = C^{k+1}u yields C^{(k+1)+g(ℓ)}u. But mφ,1_ℓ consists of one C→λ followed by one C→C^{g(ℓ)+1}; the net effect is to add g(ℓ)−1 copies of C, so the actual result is C^{k+g(ℓ)}u. Consequently, the subsequent application of mφ,2_{ℓ′→f} requires k+g(ℓ) = ℓ′+g(ℓ′)+1, not k+g(ℓ) = ℓ′+g(ℓ′) as used in the modular argument. With 1 ≤ k, ℓ, ℓ′ ≤ v, the correct congruence has the solution k = ℓ+1, ℓ′ = ℓ, so the failure matrices of vertex ℓ can fire when the encoded vertex is ℓ+1 and Yℓ is absent. Equivalently, in the intended case k = ℓ = 1 the chain cannot start, because C^{v+1} is one occurrence short of the required threshold v+2. Thus the claimed invariant (state(w) = current vertex of GC) is not maintained, and L(G) ⊇ L(G′) is not proved as written. The error appears local—for example, replacing C→C^{g(ℓ)+1} by C→C^{g(ℓ)+2}—so it may be repairable, but Theorem 9's central claim is currently unsupported.","section":"Section 6, Theorem 9"},{"comment":"The reverse inclusions in Theorems 4 and 5 are not fully established. After the Phase-2 case list, the proofs conclude with 'by a straightforward formal induction argument, one can see that the languages of G and of G′ are equal.' The preceding case analysis is informal in exactly the places where the induction hypothesis is needed: for instance, 'It is not hard to check that now, no matrix is applicable' (Theorem 4, Case 2) and 'the reasoning presented in case 1 is by large applicable' (Theorem 5, Case 3). The reader is not shown that every reachable sentential form has the normal form w = αζβ with ζ in the listed finite set after arbitrary applications of the matrices, nor that the asserted 'only applicable matrix' conclusions hold for all choices of α and β. Since these theorems are central to the paper's claimed Pareto frontier, the authors should either state an explicit invariant and prove it by complete induction or provide a detailed enumeration of the missing cases.","section":"Section 5, Theorems 4 and 5"},{"comment":"The proof of Theorem 7 says that 'the arguments from the proof of Theorem 6 nearly literally translate to this case.' This is a placeholder rather than a proof. In Theorem 7 the start symbol S is reused as the Phase-2 marker, so the invariant from Theorem 6 (a single occurrence of $ separating a {0,1}-word from a terminal part) is changed to a situation with two adjacent S's in the middle of the sentential form. One must verify explicitly that matrices r2 through r7 cannot consume or rearrange the S-pair in a way that makes the context-free simulation rγ applicable again, and that the termination matrix r7 has exactly the same behavior as its counterpart in Theorem 6. Because Theorem 7 and Corollary 1 depend on this translation, the proof should be written out in full.","section":"Section 6, Theorem 7"}],"minor_comments":[{"comment":"Near the end of Case (2), the sentence 'v′ ⇒G w or v′ ⇒G w' should distinguish the two different deletion rules (AB → λ and CC → λ); as printed, both alternatives are identical.","section":"Section 4, proof of Theorem 1"},{"comment":"There is a typo: 'This string w′3 does not correspond...' is followed by 'w′3 can be thought of being derived...' and later 'corrsponds'; these should be corrected. The same proof would also benefit from a short explanation of the claim that if α ∈ {1}∗ and β ∈ ({1}∪T)∗, then, because w ∈ LsMM, either α = β = λ or α = 1 and β ∈ {1}T∗.","section":"Section 6, proof of Theorem 8"},{"comment":"The formalism says 'the sets P and F' although P and F are strings; using 'conditions' or 'context strings' would be more precise. Also, the notation V+ ∪ {∅} should be clarified, since ∅ is not a symbol of V.","section":"Section 2, Definition 1"},{"comment":"The sketch for SSCM(4,2;4;3,3) = RE is not proved and is not listed in Table 1; it should be explicitly labeled as an informal idea or removed to avoid confusion.","section":"Section 4, Remark 1"},{"comment":"There is a typo in 'When succussful'; it should be 'When successful'.","section":"Section 6, proof of Theorem 9"}],"recommendation":"major_revision","confidential_remarks":"The Theorem 9 error is arithmetic and local rather than a sign of a fundamentally wrong approach, so I recommend major revision rather than rejection. The main revision should repair the failure-case simulation and expand the delegated inductions in Theorems 4–7. I see no concerns about attribution or scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper is a real contribution to the descriptional complexity of semi-conditional matrix grammars. Theorems 1–3 give genuinely new RE-completeness bounds for simple grammars—degree (2,1) with five nonterminals, degree (3,1) with five and then four nonterminals—and the introduction of the non-simple matrix count as a sixth resource dimension is useful. The constructions are explicit, and the invariants for the reverse inclusions in Theorems 1–3 are stated carefully enough that I believe the proofs.\n\nThe soft spots are exactly where the authors wave their hands. Theorems 4 and 5 end with 'straightforward formal induction,' Theorem 7 says the arguments 'nearly literally translate,' and Theorem 8 has typos in the derivation display. Those are expositional, not necessarily fatal.\n\nThe bigger problem is Theorem 9. The failure-case simulation has an off-by-one error. Matrix mφ,1 = [(C→λ, C→C^{g(ℓ)+1}), ∅, Yℓ] applied to C^{k+1}u yields C^{k+g(ℓ)}u, not C^{(k+1)+g(ℓ)}u as the proof states. And mφ,2 requires ℓ'+g(ℓ')+1 occurrences of C, not ℓ'+g(ℓ'). Putting these together, the modular uniqueness argument becomes k+g(ℓ) = ℓ'+g(ℓ')+1, and k=ℓ+1, ℓ'=ℓ satisfies it. So the failure matrices for rule ℓ can fire when the simulated state is ℓ+1, using a red edge that belongs to vertex ℓ. That breaks the central invariant of the reverse inclusion. The fix looks simple—change C→C^{g(ℓ)+1} to C→C^{g(ℓ)+2} in mφ,1, or redefine g(ℓ)=vℓ−1—so the theorem is probably recoverable, but the proof as written is not correct.\n\nI share the reader's concern about the normal-form invariants in Section 3. The reverse inclusions for Theorems 1–3 rely on structural claims like 'CC cannot occur in Stages 1 or 2' and 'BA is never a subsequence.' They are plausible and consistent with the grammar forms, but a referee should ask for actual inductive proofs rather than 'easy inspection.' The citation pattern is fine; the paper builds on prior results honestly.\n\nBottom line: this deserves a serious referee. The first three theorems alone are worth publishing in a specialist venue, and the later trade-offs including the three-nonterminal results are likely correct after the notation is cleaned up. I'd send it out with a request to fix Theorem 9 and expand the hand-wavy inductions. I don't work directly in this area, so I won't cite it myself in the next year, but the right reader in formal language theory will want it.","headline":"Genuinely new bounds for simple semi-conditional matrix grammars, but Theorem 9's off-by-one breaks the reverse inclusion as written; likely repairable.","tokens_in":23248,"tokens_out":7760,"would_cite":false,"duration_ms":65220,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q45","68Q42"],"pacs":[],"model":"deepseek-v4-flash","headline":"Semi-conditional matrix grammars with as few as three nonterminals generate every recursively enumerable language, improving earlier resource bounds.","keywords":["semi-conditional matrix grammars","regulated rewriting","computational completeness","recursively enumerable languages","descriptional complexity","matrix grammars","normal forms","graph-controlled grammars"],"falsifier":"Exhibit a (4,2)-GNF grammar for some recursively enumerable language with a reachable sentential form, before any erasing rule is used, that contains CC or AB as a subword; that single counterexample would break the invariant on which Theorem 1's reverse inclusion rests, and analogous violations of Eqs. (1)–(5) would refute the other normal-form-based theorems.","tokens_in":22131,"feed_emoji":"📜","tokens_out":9115,"duration_ms":81802,"temperature":0.7,"pith_summary":"Semi-conditional matrix grammars are grammars whose rule blocks come with two conditions: a string that must appear in the current word and a string that must not appear. This paper asks how small such a grammar can be—in nonterminals, conditional blocks, and block length—while still generating every language that a Turing machine can accept. The answer, proved by simulation of normal-form grammars, is that very small families already reach this full power: five nonterminals with three conditional binary blocks at degree (2,1), four nonterminals with length-three blocks at degree (3,1), and, when the number of conditional blocks is unbounded, even three nonterminals. These results improve earlier bounds and map a trade-off frontier among the resource parameters.","feed_headline":"Three nonterminals still give full computational power","feed_subtitle":"New simulations show semi-conditional matrix grammars reach full computing power with as few as three nonterminals.","key_machinery":"The load-bearing object is the conditional matrix, a block of context-free rules with an attached permitting string P and forbidden string F; the block applies to a word w only if P occurs in w and F does not. In the main constructions, a fresh marker # is introduced by one matrix replacing the nonterminals that the original erasing rule would delete, and a second matrix deletes the markers; the strings P and F are chosen so that this two-phase action fires exactly when the original rule (e.g., AB→λ, CC→λ, BBB→λ, AA→λ, 0$0→$, or 1$1→$) is enabled. The normal forms of Geffert and of Masopust–Meduna provide the invariant that certain subwords are absent during the context-free phase, and this invariant is what the forbidden strings check. Theorem 9 replaces the normal-form approach with a simulation of a two-nonterminal graph-controlled grammar, encoding the current vertex as a unary block of a third nonterminal C and using long matrices of C→λ deletions, bounded by a forbidden block of C's, to test the state exactly.","core_discovery":"The paper claims that the classes SSCM(2,1;5;3,2), SSCM(3,1;5;2,2), SSCM(3,1;4;3,3), SCM(4,3;4;7,2,6), SCM(5,2;4;7,2,4), SCM(6,3;4;7,2,3), SCM(6,3;3;*,2,4), SCM(7,2;3;*,2,3), and SSCM(0,*;3;*,*) all equal RE, the class of recursively enumerable languages. Each equality is proved by taking a type-0 grammar in a known normal form and simulating its two non-context-free erasing rules with conditional matrices. The reverse inclusion is the delicate part: an induction on derivation length shows that every sentential form the simulating grammar can reach either is an ordinary sentential form of the original grammar or is a marked version of one, with the marker placed exactly where the erasing rule would act. The forbidden strings in the matrices enforce the normal-form invariants—for instance, that CC never appears while S is still present—which is what blocks spurious simulations.","pith_inferences":["Because the simulations in Theorems 1–8 do not depend on the order of rules inside a matrix, the same completeness results should carry over to unordered-matrix semi-conditional grammars (SCUM); the paper notes this for most of its constructions, so a formal transfer seems within reach.","The unary state-encoding idea behind Theorem 9 is a general trick: any controlled-rewriting model whose control can be encoded as a bounded block of symbols may be simulated with a third nonterminal by testing block length with long forbidden strings, suggesting analogous three-nonterminal completeness results for other grammar control mechanisms.","A natural next target is lower bounds: if the Pareto frontier is strict, then, e.g., SSCM(2,1;4;3,2) or SSCM(3,1;4;2,2) should fail to contain RE, and the constructions here give concrete candidates for where the threshold lies.","The six-parameter notation (i,j;n;m,ℓ,s) makes the trade-offs explicit; future work could focus on minimizing the number of long matrices rather than total conditional matrices, as the authors mention."],"forward_implications":["Semi-conditional matrix grammars of degree (2,1) with five nonterminals, three conditional matrices, and matrix length at most two characterize RE (Theorem 1).","At degree (3,1), four nonterminals and three conditional matrices of length three are enough to characterize RE (Theorem 3).","If the simplicity condition is relaxed to allow non-simple conditional matrices, the number of nonterminals drops to three while keeping matrix length two, at the price of more conditional matrices or a higher degree (Theorems 6–8).","With an unbounded number of conditional matrices, three nonterminals suffice even for simple grammars; the simulation of two-nonterminal graph-controlled grammars yields SSCM(0,*;3;*,*) = RE (Theorem 9).","The existing bound SSCM(3,1;7;2,3) = RE is improved in several directions, and the table of results delineates a resource trade-off frontier, leaving lower bounds as the natural next question."],"supporting_citations":[{"why":"Supplies Geffert's (5,2)-GNF and its stage structure, the base normal form from which (4,2)- and (3,2)-GNF are derived.","marker":"[11]"},{"why":"Introduces the Masopust–Meduna normal form (MMNF) with shrinking rules 0$0→$, 1$1→$, $→λ used by Theorems 2, 6, 7, and 8.","marker":"[14]"},{"why":"Provides the modified MMNF (MMMNF) and the framework for counting non-simple rules, used in Theorem 2 and the SCM notation.","marker":"[9]"},{"why":"Establishes the prior completeness result SSCM(3,1;7;2,3)=RE that this paper improves.","marker":"[16]"},{"why":"Defines semi-conditional matrix grammars and the permitting/forbidden condition mechanism, and gives the early (0,2) result for comparison.","marker":"[17]"},{"why":"Shows graph-controlled grammars with only two nonterminals characterize RE, the starting point for Theorem 9's simulation.","marker":"[6]"}],"fun_headline_variants":["Semi-conditional matrix grammars reach full power with just 3 nonterminals","Tiny semi-conditional grammars simulate all computable languages","Three nonterminals and short conditions suffice for RE completeness","Minimal semi-conditional matrix grammars generate every r.e. language","Resource-light semi-conditional matrix grammars hit Turing-complete"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proofs assume that the normal-form grammars have strict structural invariants—for instance, that while the start symbol S is still present, strings like CC never occur as subwords—and that the cited two-nonterminal graph-controlled grammar theorem is correct; if either gives way, the reverse inclusions of the main theorems collapse.","fun_headline_variants_meta":{"raw":{"variants":["Semi-conditional matrix grammars reach full power with just 3 nonterminals","Tiny semi-conditional grammars simulate all computable languages","Three nonterminals and short conditions suffice for RE completeness","Minimal semi-conditional matrix grammars generate every r.e. language","Resource-light semi-conditional matrix grammars hit Turing-complete"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000143,"raw_usage":{"total_tokens":1234,"prompt_tokens":1069,"completion_tokens":165,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":685,"completion_tokens_details":{"reasoning_tokens":73}},"tokens_in":685,"tokens_out":165,"duration_ms":2511,"temperature":1.0,"reasoning_tokens":73,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:26:50.037534+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a (4,2)-GNF grammar for some recursively enumerable language with a reachable sentential form, before any erasing rule is used, that contains CC or AB as a subword; that single counterexample would break the invariant on which Theorem 1's reverse inclusion rests, and analogous violations of Eqs. (1)–(5) would refute the other normal-form-based theorems.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Geffert's (5,2)-GNF and its stage structure, the base normal form from which (4,2)- and (3,2)-GNF are derived."},{"cited_title":"Masopust and A","cited_arxiv_id":null,"evidence_quote":"Introduces the Masopust–Meduna normal form (MMNF) with shrinking rules 0$0→$, 1$1→$, $→λ used by Theorems 2, 6, 7, and 8."},{"cited_title":"Fernau, L","cited_arxiv_id":null,"evidence_quote":"Provides the modified MMNF (MMMNF) and the framework for counting non-simple rules, used in Theorem 2 and the SCM notation."},{"cited_title":"Meduna and T","cited_arxiv_id":null,"evidence_quote":"Establishes the prior completeness result SSCM(3,1;7;2,3)=RE that this paper improves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines semi-conditional matrix grammars and the permitting/forbidden condition mechanism, and gives the early (0,2) result for comparison."},{"cited_title":"Fernau, R","cited_arxiv_id":null,"evidence_quote":"Shows graph-controlled grammars with only two nonterminals characterize RE, the starting point for Theorem 9's simulation."}],"review_version":1}