Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 58 min ago
PreprintCC BY 4.0arXiv

Non-Terminal Complexity of Simple Semi-Conditional Grammars

  • Henning Fernau
  • Sanjay Jain
  • Linus Richter
  • Frank Stephan
  • Dan Turetsky
Open at sourcePDFDOICite

Abstract

We study the complexity of simple semi-conditional grammars (SSCGs) in terms of the number of their terminals and non-terminals. We show that SSCGs with three non-terminals can generate all RE languages; two non-terminals suffice for linear languages; and one suffices for unary regular languages. We also determine both upper bounds and fundamental limitations of SSCGs: while certain one-non-terminal SSCGs can generate non-context-free languages, every language generated by a one-non-terminal SSCG is in non-deterministic linear space. We also prove that there exists a regular language of alphabet size at least 3 which cannot be generated by any one-non-terminal SSCG. Finally, we prove that membership testing for SSCGs of two non-terminals is already NP-hard.

Related

  1. Algebraic Vector Fields of Connected Semi-simple Matrix Groups are 3-generated
    Yiyang Jiang, Xudong Chen
    arXivPreprintarXiv licenceFull textAlgebra & number theoryAnalysis & PDEsarXiv
  2. Automorphism groups of semi-rigid T-varieties of complexity one
    Kirill Rassolov
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  3. A Simple Complexity Lower Bound for Solving Ax=b
    Ohad Shamir
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingOptimisation & controlarXiv
  4. An Efficient Automated Geometry Reasoning Method via Knowledge Merging and Semi-Conditional Rules
    Qixin Zhou, Siran Lei, Ying Wang +2
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  5. Grouped Semi-Supervised Estimation of Two-Sample Functionals via Single-Index Conditional Imputation
    Hengyao Xu, Tao Tan
    arXivPreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{fernau2026nonterminal,
  title = {{Non-Terminal Complexity of Simple Semi-Conditional Grammars}},
  author = {Henning Fernau and Sanjay Jain and Linus Richter and Frank Stephan and Dan Turetsky},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.14181},
  eprint = {2609.14181},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.14181},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Non-Terminal Complexity of Simple Semi-Conditional Grammars
AU  - Henning Fernau
AU  - Sanjay Jain
AU  - Linus Richter
AU  - Frank Stephan
AU  - Dan Turetsky
PY  - 2026
DA  - 2026/09/12
PB  - arXiv
DO  - 10.48550/arxiv.2609.14181
UR  - https://arxiv.org/abs/2609.14181
AB  - We study the complexity of simple semi-conditional grammars (SSCGs) in terms of the number of their terminals and non-terminals. We show that SSCGs with three non-terminals can generate all RE languages; two non-terminals suffice for linear languages; and one suffices for unary regular languages. We also determine both upper bounds and fundamental limitations of SSCGs: while certain one-non-terminal SSCGs can generate non-context-free languages, every language generated by a one-non-terminal SSCG is in non-deterministic linear space. We also prove that there exists a regular language of alphabet size at least 3 which cannot be generated by any one-non-terminal SSCG. Finally, we prove that membership testing for SSCGs of two non-terminals is already NP-hard.
ER  -