โ Scribed by Greibach, Sheila A.
No coin nor oath required. For personal study only.
There is a context-free language L0 such that every context-flee language is an inverse homomorphic image of Lo or Lo {e}. Hence the time complexity of recognition of Lo is the least upper bound for time complexity of recognition of context-free languages. A similar result holds for quasirealtime Turing machine languages. Several languages are given such that deterministic and nondeterministic polynomial time acceptance are equivalent if and only if any one of them is deterministic polynomial time acceptable.
๐ SIMILAR VOLUMES
A bracketed grammar is a context-free grammar in which indexed brackets are inserted around the right-hand sides of the rules. The language generated by a bracketed grammar is a bracketed language. An algebraic condition is given for one bracketed language to be a subset of another. The intersection
This paper demonstrates that the P-complete language of yes-instances of Circuit Value Problem under a suitable encoding can be generated by a linear conjunctive grammar, or, equivalently, accepted by a triangular trellis automaton. This result has several implications on the properties of the langu