Elamur Research⌕
☰
home / papers / 2026 / On Natural Language Stringsets, Senses, and Generative Capacity

On Natural Language Stringsets, Senses, and Generative Capacity

Paper · 2026 · Daniel Radzinski

Summary

This squib re-examines the weak generative capacity (WGC) arguments that natural language is not context-free. Its main target is the Swiss German cross-serial verb raising proof of Huybregts (1984) and Shieber (1985), which textbooks have long treated as settled. Radzinski shows that such intersection-based proofs fail once unintended readings of strings are allowed. If a sequence like Hans em Hans is read as a proper name, a supposedly ill-formed sentence becomes grammatical, and the intersection of the regular language with Swiss German becomes context-free. Because names and direct quotation can license nearly any word sequence, bare orthographic stringsets may approach Σ*. The proposed fix adopts Miller's view of a word as a pairing of form and sense. Each token is written as its spelling joined to a unique WordNet sense identifier. With such sense-tagged vocabularies, the classic arguments hold again and stay within WGC, since they rely on neither trees nor part-of-speech. The contribution makes explicit an assumption that earlier proofs silently depended on.

Key points

  • The corrected Swiss German intersection T (after Manaster Ramer and Ojeda 1988) requires the dative em Hans count to stay at or below the count of hälfe. Admitting Hans em Hans as a name yields instead a language U, homomorphic to {aⁿbᵐ : 1 ≤ n ≤ m}, which is context-free.
  • The paper extends Stabler's (2019) direct-quotation objection to proper names in general. Oddly formed racehorse names illustrate the point, and orthography-only stringsets could be merely regular.
  • Senses are encoded with WordNet Database Location (DL) IDs, e.g. bag02776042 and box02886585. The author argues that differences in sense granularity across controlled vocabularies barely affect such proofs.
  • Under the reformulation, Dutch is weakly non-context-free just like Swiss German, despite lacking overt case. Following Michaelis and Kracht (1997), Dutch is also non-semilinear.
  • Chinese as a whole, not only its number-names, is not well-behaved semilinear, and therefore not context-free, tree adjoining, or multiple context-free. The author recommends that future proofs state that their strings carry sense content.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

Cite

Cite as Daniel Radzinski. 2026. On Natural Language Stringsets, Senses, and Generative Capacity. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/coli.a.21

@article{radzinski2026natural,
  title = {{On Natural Language Stringsets, Senses, and Generative Capacity}},
  author = {Daniel Radzinski},
  journal = {Computational Linguistics},
  year = {2026},
  doi = {10.1162/coli.a.21},
  url = {https://doi.org/10.1162/coli.a.21}
}

References

13 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Culy, Christopher. 1985. The complexity of the vocabulary of Bambara. Linguistics and Philosophy, 8:345–351. https://doi.org/10.1007/BF00630918 — [doi:10.1007/bf00630918](https://doi.org/10.1007/bf00630918) ↗
  2. Dolatian, Hossep, Jonathan Rawski, and Jeffrey Heinz. 2021. Strong generative capacity of morphological processes. In Proceedings of the Society for Computation in Linguistics 2021, pages 228–243. https://doi.org/10.7275/sckf-8f46 ↗
  3. Groenink, Annius V. 1997. Mild context-sensitivity and tuple-based generalizations of context-free grammar. Linguistics and Philosophy, 20:607–636. https://doi.org/10.1023/A :1005376413354 Hopcroft, John E. and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. — [doi:10.1023/a](https://doi.org/10.1023/a) find
  4. Addison-Wesley. Huybregts, Riny. 1984. The weak inadequacy of context-free phrase structure grammars. find
  5. In Ger de Haan, Mieke Trommelen, and Wim Zonneveld, editors, Van Periferie naar Kern, pages 81–99. Foris. Ibarra, Oscar H. and Ian McQuillan. 2020. Semilinearity of families of languages. International Journal of Foundations of Computer Science, 31:1179–1198. https://doi.org/10.1142 /S01290541204200… find
  6. Prentice Hall. Kanazawa, Makoto. 2009. The pumping lemma for well-nested multiple context-free languages. In V. Diekert and D. Nowotka, editors, Developments in Language Theory: 13th International Conference, Lecture Notes in Computer Science, volume 5583, pages 312–325. Springer. https://doi.org/10… — [doi:10.1007/978](https://doi.org/10.1007/978) find
  7. Melamud, Oren, Jacob Goldberger, and Ido Dagan. 2016. Context2vec: Learning generic context embedding with bidirectional LSTM. In Proceedings of the 20th SIGNLL Conference on Computational Natural Language Learning, pages 51–61. https://doi.org/10.18653/v1/K16 -1006 Michaelis, Jens and Marcus Kracht… ↗
  8. Ojeda, Almerindo. 1988. A linear precedence account of cross-serial dependencies. Linguistics and Philosophy, 11:457–492. https://doi.org/10.1007/BF00668683 Pagin, Peter and Dag Westerståhl. 2010. Pure quotation and general compositionality. Linguistics and Philosophy, 33:381–415. https://doi.org/… — [doi:10.1007/s10988-011](https://doi.org/10.1007/s10988-011) ↗
  9. H., Alice ter Meulen, and Robert E. Wall. 1990. Mathematical Methods in Linguistics. find
  10. Kluwer. Pullum, Geoffrey K. and Gerald Gazdar. 1982. Natural languages and context-free languages. Linguistics and Philosophy, 4:471–504. https://doi.org/10.1007/BF00360802 Pullum, Geoffrey K. and Kyle Rawlins. 2007. Argument or no argument? Linguistics and Philosophy, 30:277–287. https://doi.org /… — [doi:10.1007/s10988-007-9013-y](https://doi.org/10.1007/s10988-007-9013-y) ↗
  11. Radzinski, Daniel. 1991. Chinese number-names, tree adjoining languages, and mild context-sensitivity. Computational Linguistics, 17:277–299. find
  12. Seki, Hiroyuki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. 1991. On multiple context-free grammars. Theoretical Computer Science, 88:191–229. https://doi.org/10.1016/0304 -3975(91)90374-B Shieber, Stuart. 1985. Evidence against the context-freeness of natural language. Linguistics and Philos… — [doi:10.1016/0304](https://doi.org/10.1016/0304) ↗
  13. Stabler, Edward P. 2019. Three mathematical foundations for syntax. Annual Review of Linguistics, 5:243–260. https://doi.org/10.1146/annurev-linguistics -011415-040658 Wang, Shunjie and Shane Steinert-Threlkeld. 2023. Evaluating transformer’s ability to learn mildly context-sensitive languages. In… — [doi:10.1146/annurev-linguistics](https://doi.org/10.1146/annurev-linguistics) ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/radzinski-2026-natural-language-stringsets-senses-generative/