EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On pumping constants and smallest grammars for context-free languages. Part II—Greibach normal form

Hermann Gruber, Markus Holzer

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →