The interchange or pump (DI)lemmas for context-free languages

R. Boonyavatana, G. Slutzki

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

In this paper we compare the interchange condition of Ogden, Ross and Winklmann to various pumping conditions: the classic pumping condition, Ogden's condition, generalized Ogden's condition, linear versions of the above conditions and the Sokolowski-type conditions. In addition, we formulate an interchange condition for linear context-free languages and compare it with the other conditions. Our results show that the interchange conditions are incomparable with the various pumping conditions, they are strictly stronger than Sokolowski's condition, and are incomparable to the extended Sokolowski's condition.

Original languageEnglish
Pages (from-to)321-338
Number of pages18
JournalTheoretical Computer Science
Volume56
Issue number3
DOIs
StatePublished - Mar 1988

Fingerprint Dive into the research topics of 'The interchange or pump (DI)lemmas for context-free languages'. Together they form a unique fingerprint.

  • Cite this