EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Pumping Lemmas Can be “Harmful”

Jingnan Xie, Harry B. Hunt III, Richard E. Stearns

Theory of Computing Systems · 2024-10 · 68 (5) · 1339-1352

DOI: 10.1007/s00224-024-10169-9 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Theory of Computing Systems, online erschienen am 05.04.2024. Verfasst von Jingnan Xie und 2 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 20 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A pumping lemma for a class of languages $$\varvec{\mathcal {C}}$$ C is often used to show particular languages are not in $$\varvec{\mathcal {C}}$$ C . In contrast, we show that a pumping lemma for a class of languages $$\varvec{\mathcal {C}}$$ C can be used to study the computational complexity of the predicate “ $$\in \varvec{\mathcal {C}}$$ ∈ C ” via highly efficient many-one reductions. In this paper, we use extended regular expressions (EXREGs, introduced in Câmpeanu et al. (Int. J. Foundations Comput. Sci. 14 (6), 1007–1018, 2003)) as an example to illustrate the proof technique and establish the complexity of the predicate “is an EXREG language” for several classes of languages. Due to the efficiency of the reductions, both productiveness (a stronger form of non-recursive enumerability) and complexity results can be obtained simultaneously. For example, we show that the predicate “is an EXREG language” is productive (hence, not recursively enumerable) for context-free grammars, and is Co-NEXPTIME-hard for context-free grammars generating bounded languages. The proof technique is easy to use and requires only a few conditions. This suggests that for any class of languages $$\varvec{\mathcal {C}}$$ C having a pumping lemma, the language class comparison problems (e.g., does a given context-free grammar generate a language in $$\varvec{\mathcal {C}}$$ C ?) are almost guaranteed to be hard. So, pumping lemmas sometimes could be “harmful” when studying computational complexity results.

Zitieren

APA

Xie, J., III, H. B. H., & Stearns, R. E. (2024). Pumping Lemmas Can be “Harmful”. Theory of Computing Systems, 68(5), 1339-1352. https://doi.org/10.1007/s00224-024-10169-9

Vancouver

Xie J, III HBH, Stearns RE. Pumping Lemmas Can be “Harmful”. Theory of Computing Systems. 2024;68(5):1339-1352. doi:10.1007/s00224-024-10169-9

BibTeX
@article{Xie2024,
  author = {Xie, Jingnan and III, Harry B. Hunt and Stearns, Richard E.},
  title = {Pumping Lemmas Can be “Harmful”},
  journal = {Theory of Computing Systems},
  year = {2024},
  volume = {68},
  number = {5},
  pages = {1339--1352},
  doi = {10.1007/s00224-024-10169-9}
}
Kostenlos starten →