๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The hardest linear conjunctive language

โœ Scribed by Alexander Okhotin

Book ID
104136927
Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
190 KB
Volume
86
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 languages generated by conjunctive grammars of the general form and on the relationship between the abstract models of parallel computation.

๐Ÿ“œ SIMILAR VOLUMES

The Hardest Context-Free Language
The Hardest Context-Free Language
โœ Greibach, Sheila A. ๐Ÿ“‚ Article ๐Ÿ“… 1973 ๐Ÿ› Society for Industrial and Applied Mathematics ๐ŸŒ English โš– 772 KB

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 Tu

On the closure properties of linear conj
On the closure properties of linear conjunctive languages
โœ Alexander Okhotin ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 234 KB

Linear conjunctive grammars are conjunctive grammars in which the body of each conjunct contains no more than a single nonterminal symbol. They can at the same time be thought of as a special case of conjunctive grammars and as a generalization of linear context-free grammars that provides an explic

On the growth of linear languages
On the growth of linear languages
โœ Tullio Ceccherini-Silberstein ๐Ÿ“‚ Article ๐Ÿ“… 2005 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 126 KB