Comparisons of Parikh’s conditions to other conditions for context-free languages

TitleComparisons of Parikh’s conditions to other conditions for context-free languages
Publication TypeJournal Article
Year of Publication1998
AuthorsG. Ramos, J. Lopez, and R. Morales
JournalTheoretical Computer Science
Volume202
Number1-2
Pagination231-244
PublisherElsevier
ISSN Number0304-3975
Abstract

  this paper we first compare Parikh’s condition to various pumping conditions - Bar- Hillel’s pumping lemma, Ogden’s condition and Bader-Moura’s condition; secondly, to interchange condition; and finally, to Sokolowski’s and Grant“s conditions. In order to carry out these comparisons we present some properties of Parikh’s languages. The main result is the orthogonality of the previously mentioned conditions and Parikh’s condition. In

Citation KeyGonzaloRamos1998
Paper File: 
https://www.nics.uma.es/sites/default/files/papers/GonzaloRamos1998.pdf