The interchange or pump (di)lemmas for context-free languages (Q1104760)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The interchange or pump (di)lemmas for context-free languages |
scientific article; zbMATH DE number 4057032
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The interchange or pump (di)lemmas for context-free languages |
scientific article; zbMATH DE number 4057032 |
Statements
The interchange or pump (di)lemmas for context-free languages (English)
0 references
1988
0 references
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.
0 references
interchange condition
0 references
pumping conditions
0 references
linear context-free languages
0 references
Sokolowski's condition
0 references
0 references
0.8653737306594849
0 references
0.8272679448127747
0 references
0.8146712183952332
0 references
0.7970560193061829
0 references
