TY - JOUR
T1 - The interchange or pump (DI)lemmas for context-free languages
AU - Boonyavatana, R.
AU - Slutzki, G.
PY - 1988/3
Y1 - 1988/3
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0023979734&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(88)90138-7
DO - 10.1016/0304-3975(88)90138-7
M3 - Article
AN - SCOPUS:0023979734
SN - 0304-3975
VL - 56
SP - 321
EP - 338
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 3
ER -