Paper Info
Title
Comparisons of Parikh's condition to other conditions for context-free languages
Abstract
In 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.
Year
DOI
Venue
1998
10.1016/S0304-3975(97)00262-4
Theor. Comput. Sci.
Keywords
DocType
Volume
Context-free languages,Pumping lemmas,Sokolowski's and Grant's condition,Interchange condition,Parikh's condition,context-free language
Journal
202
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
G. Ramos-Jiménez100.34
J. López-Muñoz200.34
R. Morales-Bueno3173.80