REVIEW 2 cited by
Pumping lemmas for linear and nonlinear context-free languages
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
Pumping lemmas are created to prove that given languages are not belong to certain language classes. There are several known pumping lemmas for the whole class and some special classes of the context-free languages. In this paper we prove new, interesting pumping lemmas for special linear and context-free language classes. Some of them can be used to pump regular languages in two place simultaneously. Other lemma can be used to pump context-free languages in arbitrary many places.
Forward citations
Cited by 2 Pith papers
-
On the Complexity of Language Membership for Probabilistic Words
Probabilistic membership for context-free languages is in PTIME for unambiguous and poly-slicewise-unambiguous languages, #P-hard for some unions of two linear unambiguous CFLs, and tractable via complement-capable ci...
-
A Myhill-Nerode Type Characterization of 2detLIN Languages
A language is 2detLIN if and only if it has a finite, complete, crossing-free prefix-suffix classification.
Discussion (0). Continue with ORCID to comment.