The interchange or pump (di)lemmas for context-free languages (Q1104760): Difference between revisions

We compare the interchange condition of \textit{W. Ogden}, \textit{R. J. Ross} and \textit{K. Winklmann} [SIAM J. Comput. 14, 410-415 (1985; Zbl 0601.68051)] 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 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.