TY - JOUR
T1 - Comparisons between some pumping conditions for context-free languages
AU - Hewett, R.
AU - Slutzki, G.
PY - 1988/12
Y1 - 1988/12
N2 - We present a systematic investigation of the relationships between various pumping properties-the classic pumping condition of Bar-Hillel et al., Ogden's condition, a generalized Ogden condition of Bader and Moura, Sokolowski's condition, an extended Sokolowski condition of Grant, and linear versions of some of these conditions. We define special language operations that allow us to produce, in a systematical and uniform way, languages that satisfy some combinations of the pumping conditions but not the others. We show, among others, that the general and the linear pumping conditions are "orthogonal," whereas the generalized Ogden condition is stronger than the extended Sokolowski condition.
AB - We present a systematic investigation of the relationships between various pumping properties-the classic pumping condition of Bar-Hillel et al., Ogden's condition, a generalized Ogden condition of Bader and Moura, Sokolowski's condition, an extended Sokolowski condition of Grant, and linear versions of some of these conditions. We define special language operations that allow us to produce, in a systematical and uniform way, languages that satisfy some combinations of the pumping conditions but not the others. We show, among others, that the general and the linear pumping conditions are "orthogonal," whereas the generalized Ogden condition is stronger than the extended Sokolowski condition.
UR - http://www.scopus.com/inward/record.url?scp=0346946574&partnerID=8YFLogxK
U2 - 10.1007/BF02088014
DO - 10.1007/BF02088014
M3 - Article
AN - SCOPUS:0346946574
SN - 0025-5661
VL - 21
SP - 223
EP - 233
JO - Mathematical Systems Theory
JF - Mathematical Systems Theory
IS - 1
ER -