On pumping constants and smallest grammars for context-free languages. Part II—Greibach normal form
Semigroup Forum · 07.07.2026
DOI: 10.1007/s00233-026-10653-3 ↗Kurz gefasst
Fachartikel in der Zeitschrift Semigroup Forum, online erschienen am 07.07.2026. Verfasst von Hermann Gruber und 1 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Justus-Liebig-Universität Gießen.
Abstract (Originalsprache)
We continue our research, started in [H. Gruber and M. Holzer. On pumping constants and smallest grammars for context-free languages, LNCS 15840, pp. 54–68, 2025], on the relation between context-free grammar size and minimal pumping constants w.r.t. Bar-Hillel’s pumping lemma, now considering the case when the language is described by a grammar in Greibach normal form.
Förderung
- Justus-Liebig-Universität Gießen
Zitieren
APA
Gruber, H., & Holzer, M. (2026). On pumping constants and smallest grammars for context-free languages. Part II—Greibach normal form. Semigroup Forum. https://doi.org/10.1007/s00233-026-10653-3
Vancouver
Gruber H, Holzer M. On pumping constants and smallest grammars for context-free languages. Part II—Greibach normal form. Semigroup Forum. 2026. doi:10.1007/s00233-026-10653-3
BibTeX
@article{Gruber2026,
author = {Gruber, Hermann and Holzer, Markus},
title = {On pumping constants and smallest grammars for context-free languages. Part II—Greibach normal form},
journal = {Semigroup Forum},
year = {2026},
doi = {10.1007/s00233-026-10653-3}
}
EUVIMED