The Hardest Language for Conjunctive Grammars



: Okhotin A

: Alexander S. Kulikov, Gerhard J. Woeginger

: International Computer Science Symposium in Russia

Publisher: SPRINGER INT PUBLISHING AG, GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND

: 2016

: Computer Science – Theory and Applications

: COMPUTER SCIENCE - THEORY AND APPLICATIONS, CSR 2016

: LECT NOTES COMPUT SC

: Lecture Notes in Computer Science

: 9691

: 340

: 351

: 12

: 978-3-319-34170-5

: 978-3-319-34171-2

: 0302-9743

DOI: https://doi.org/10.1007/978-3-319-34171-2_24


A famous theorem by Greibach ("The hardest context-free language", SIAM J. Comp., 1973) states that there exists such a context-free language L-0 that every context-free language over any alphabet is reducible to L-0 by a homomorphic reduction-in other words, is representable as an inverse homomorphic image h(-1) (L-0), for a suitable homomorphism h. This paper establishes similar characterizations for conjunctive grammars, that is, for grammars extended with a conjunction operator.



Last updated on 2024-26-11 at 17:55