On Computational Completeness of Semi-Conditional Matrix Grammars

Henning Fernau; Indhumathi Raman; Lakshmanan Kuppusamy

REVIEW 3 major objections 5 minor 17 references

On Computational Completeness of Semi-Conditional Matrix Grammars

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Semi-conditional matrix grammars with as few as three nonterminals generate every recursively enumerable language, improving earlier resource bounds.

desk verdict Genuinely new bounds for simple semi-conditional matrix grammars, but Theorem 9's off-by-one breaks the reverse inclusion as written; likely repairable. read the letter →

arxiv 2411.15338 v1 pith:WIVYA4GN submitted 2024-11-22 cs.FL

Henning Fernau , Lakshmanan Kuppusamy , Indhumathi Raman This is my paper · ORCID

classification cs.FL MSC 68Q4568Q42

keywords semi-conditionalmatrixgrammarsregulatedrewritingcomputationalcompletenessrecursivelyenumerablelanguagesdescriptionalcomplexitynormalformsgraph-controlled

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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

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.

The 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.

The 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.

I 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.

Bottom 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.

Referee Report

3 major / 5 minor

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.

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 (3)

[Section 6, Theorem 9] 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 5, Theorems 4 and 5] 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 6, Theorem 7] 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.

minor comments (5)

[Section 4, proof of Theorem 1] 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 6, proof of Theorem 8] 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 2, Definition 1] 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 4, Remark 1] 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 6, proof of Theorem 9] There is a typo in 'When succussful'; it should be 'When successful'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: each theorem constructs a new SCM/SSCM grammar from an independently established normal form; the one load-bearing self-citation is an independent prior theorem about a different grammar model.

full rationale

The paper's derivation chain is self-contained in the relevant sense. Every main theorem (Theorems 1-3, 4-6, 7-8, 9) begins from an independently established normal-form characterization of RE (Geffert (5,2)-GNF, the derived (4,2)- and (3,2)-GNFs, MMNF/sMMNF/MMMNF, all from prior literature with published proofs), and then gives an explicit SCM or SSCM grammar whose correctness is argued by induction on derivation length against structural invariants read off the normal-form sentential forms. These invariants are properties of the source grammar, not assumptions of the target result, so the reverse inclusions do not reduce to the completeness claim being proved. Theorem 9 invokes [6, Thm. 4] that graph-controlled grammars with two nonterminals characterize RE; this is co-authored by the first author, but it is a theorem about a different regulated-rewriting model, with its own proof, and is used as an input to the simulation rather than as a justification of the simulation's correctness. No parameter is fitted to data, no definition quantifies over the class being established, and no known result is merely renamed or repackaged. The proof text of Theorem 9 appears to contain a genuine counting error (the effect of m_{phi,1} on C-exponents is stated as C^{(k+1)+g(l)} whereas the two rules C->lambda and C->C^{g(l)+1} give C^{k+g(l)}, and the stated length of m_{phi,2} is off by one); this is a correctness risk, not a circularity, and does not affect the circularity score.

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

The paper introduces no physical or mathematical entities beyond the grammar constructions themselves. The free parameter g(ℓ) is an internal construction choice, not a fitted quantity. All axioms are established theorems from the cited literature; the main risk is whether the normal-form invariants hold as stated for every reachable sentential form, since the proofs depend on them.

free parameters (1)

g(ℓ) = v·ℓ = vℓ (v = number of vertices of the graph-controlled grammar)
Chosen by hand in Theorem 9's failure-case matrix m^φ,1 to make the state-consistency check injective; any sufficiently large value would work, so it is a construction choice rather than a fitted constant.

assumptions (4)

standard math Geffert (5,2)-GNF: every RE language is generated by a type-0 grammar with nonterminals {S,A,B,C,D} and deletion rules AB→λ, CD→λ (Proposition 1).
Established in [11]; used as the starting point for deriving the other normal forms used in the proofs.
standard math (4,2)-GNF and (3,2)-GNF normal forms with the specific sentential form invariants (Propositions 2 and 3, Eqs. (2) and (3)).
Derived in [11] and [14]; the invariants (e.g., no AB/CC while S is present, BA never a subsequence) are load-bearing for the inductions in Theorems 1 and 3.
standard math Masopust-Meduna normal form (MMNF) and strong/modified variants (Propositions 4 and 5, Eqs. (4) and (5)).
From [14] and [9]; the strong MMNF encoding is used in Theorems 2, 6, 7, and 8.
standard math Graph-controlled grammars with two nonterminals generate all RE languages ([6, Thm. 4]).
Used as the basis for Theorem 9; it is a published result, with one co-author overlapping the current authors, but it is not derived in this paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Computational Completeness of Semi-Conditional Matrix Grammars." pith.science (2026). https://pith.science/paper/WIVYA4GN

@misc{pith2026241115338,
  author       = {Pith},
  title        = {Pith review of: On Computational Completeness of Semi-Conditional Matrix Grammars},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WIVYA4GN}},
  note         = {Machine review of arXiv:2411.15338}
}

abstract

Matrix grammars are one of the first approaches ever proposed in regulated rewriting, prescribing that rules have to be applied in a certain order. Originally, they have been introduced by \'Abrah\'am on linguistic grounds. In traditional regulated rewriting, the most interesting case shows up when all rules are context-free. Typical descriptional complexity measures incorporate the number of nonterminals or the matrix length, i.e., the number of rules per matrix. When viewing matrices as program fragments, it becomes natural to consider additional applicability conditions for such matrices. Here, we focus on attaching a permitting and a forbidden string to every matrix in a matrix grammar. The matrix is applicable to a sentential form~$w$ only if the permitting string is a subword in~$w$ and the forbidden string is not a subword in~$w$. We call such a grammar, where the application of a matrix is conditioned as described, a semi-conditional matrix grammar. We consider $(1)$ the maximal lengths of permitting and forbidden strings, $(2)$ the number of nonterminals, $(3)$ the number of conditional matrices, $(4)$ the maximal length of any matrix and $(5)$ the number of conditional matrices with nonempty permitting and forbidden strings, as the resources (descriptional complexity measures) of a semi-conditional matrix grammar. In this paper, we show that certain semi-conditional matrix grammar families defined by restricting resources can generate all of the recursively enumerable languages.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

S. Ábrahám. Some questions of phrase-structure grammars , I. Comput. Linguistics, 4:61–70, 1965. 24 H. Fernau, L. Kuppusamy, I. Raman

work page 1965
[2]

Cremers and O

A. Cremers and O. Mayer. On matrix languages. Information and Control (now Information and Computation) , 23:86–96, 1973

work page 1973
[3]

Dassow and Gh

J. Dassow and Gh. Păun. Regulated Rewriting in Formal Language Theory , vol- ume 18 of EATCS Monographs in Theoretical Computer Science . Springer, 1989

work page 1989
[4]

H. Fernau. Nonterminal complexity of programmed grammar s. Theoretical Com- puter Science , 296:225–251, 2003

work page 2003
[5]

H. Fernau. Parsimonious computational completeness. In N. Moreira and R. Reis, editors, Developments in Language Theory - 25th International Confe rence, DLT, volume 12811 of LNCS, pages 12–26. Springer, 2021

work page 2021
[6]

Fernau, R

H. Fernau, R. Freund, M. Oswald, and K. Reinhardt. Reﬁning the nonterminal complexity of graph-controlled, programmed, and matrix gr ammars. Journal of Automata, Languages and Combinatorics , 12(1/2):117–138, 2007

work page 2007
[7]

Fernau, L

H. Fernau, L. Kuppusamy, R. O. Oladele, and I. Raman. Impro ved descriptional complexity results for simple semi-conditional grammars. Fundamenta Informati- cae, 181:189–211, 2021

work page 2021
[8]

Fernau, L

H. Fernau, L. Kuppusamy, and I. Raman. Counting simple rul es in semi-conditional grammars is not simple. In L. L. Patey and E. Pimentel, editor s, Twenty Years of Theoretical and Practical Synergies, 20th Conference on Co mputability in Europe, CiE, volume 14773 of LNCS, pages 192–204. Springer, 2024

work page 2024

Show all 17 references

[9]

Fernau, L

H. Fernau, L. Kuppusamy, and I. Raman. On the computationa l complete- ness of generalized forbidding matrix grammars. Theoretical Computer Science , 999:114539, 2024

2024
[10]

Freund, C

R. Freund, C. Martín-Vide, and Gh. Păun. From regulated r ewriting to com- puting with membranes: collapsing hierarchies. Theoretical Computer Science , 312(2-3):143–188, 2004

2004
[11]

V. Geﬀert. Normal forms for phrase-structure grammars. RAIRO Informatique théorique et Applications/Theoretical Informatics and Ap plications, 25:473–498, 1991

1991
[12]

Hauschildt and M

D. Hauschildt and M. Jantzen. Petri net algorithms in the theory of matrix gram- mars. Acta Informatica, 31:719–728, 1994

1994
[13]

Masopust

T. Masopust. A note on the generative power of some simple variants of context- free grammars regulated by context conditions. In A.-H. Ded iu, A.-M. Ionescu, and C. Martín-Vide, editors, Language and Automata Theory and Applications, LATA, volume 5457 of LNCS, pages 554–565. ...

2009
[14]

Masopust and A

T. Masopust and A. Meduna. Descriptional complexity of g eneralized forbidding grammars. In V. Geﬀert and G. Pighizzini, editors, 9th International Workshop on Descriptional Complexity of Formal Systems - DCFS , pages 170–177. University of Kosice, Slovakia, 2007

2007
[15]

A. Meduna. Generalized forbidding grammars. International Journal of Computer Mathematics, 36:31–39, 1990

1990
[16]

Meduna and T

A. Meduna and T. Kopeček. Simple semi-conditional versi ons of matrix grammars with a reduced regulating mechanism. Computing and Informatics , 23:287–302, 2004

2004
[17]

Gh. Păun. A variant of random context grammars: semi-con ditional grammars. Theoretical Computer Science , 41:1–17, 1985

1985

Pith tools

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

[1] [1]

S. Ábrahám. Some questions of phrase-structure grammars , I. Comput. Linguistics, 4:61–70, 1965. 24 H. Fernau, L. Kuppusamy, I. Raman

work page 1965

[2] [2]

Cremers and O

A. Cremers and O. Mayer. On matrix languages. Information and Control (now Information and Computation) , 23:86–96, 1973

work page 1973

[3] [3]

Dassow and Gh

J. Dassow and Gh. Păun. Regulated Rewriting in Formal Language Theory , vol- ume 18 of EATCS Monographs in Theoretical Computer Science . Springer, 1989

work page 1989

[4] [4]

H. Fernau. Nonterminal complexity of programmed grammar s. Theoretical Com- puter Science , 296:225–251, 2003

work page 2003

[5] [5]

H. Fernau. Parsimonious computational completeness. In N. Moreira and R. Reis, editors, Developments in Language Theory - 25th International Confe rence, DLT, volume 12811 of LNCS, pages 12–26. Springer, 2021

work page 2021

[6] [6]

Fernau, R

H. Fernau, R. Freund, M. Oswald, and K. Reinhardt. Reﬁning the nonterminal complexity of graph-controlled, programmed, and matrix gr ammars. Journal of Automata, Languages and Combinatorics , 12(1/2):117–138, 2007

work page 2007

[7] [7]

Fernau, L

H. Fernau, L. Kuppusamy, R. O. Oladele, and I. Raman. Impro ved descriptional complexity results for simple semi-conditional grammars. Fundamenta Informati- cae, 181:189–211, 2021

work page 2021

[8] [8]

Fernau, L

H. Fernau, L. Kuppusamy, and I. Raman. Counting simple rul es in semi-conditional grammars is not simple. In L. L. Patey and E. Pimentel, editor s, Twenty Years of Theoretical and Practical Synergies, 20th Conference on Co mputability in Europe, CiE, volume 14773 of LNCS, pages 192–204. Springer, 2024

work page 2024