patternMinor
Does a notion of a context-free complete language exist?
Viewed 0 times
notionfreeexistlanguagecompletedoescontext
Problem
Is there a notion of a context-free complete language (in the analogous sense to a $NP$-complete language)?
Solution
Yes.
Lautemann and Schwentick prove that Greibach's "hardest context-free grammar" with a neutral symbol is complete for $LOGCFL$ and hence $CFL$ also, under quantifier-free projection without BIT.
This is Corollary 4.3 in their paper
Lautemann and Schwentick prove that Greibach's "hardest context-free grammar" with a neutral symbol is complete for $LOGCFL$ and hence $CFL$ also, under quantifier-free projection without BIT.
This is Corollary 4.3 in their paper
Context
StackExchange Computer Science Q#99477, answer score: 7
Revisions (0)
No revisions yet.