A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
The Hardest Language for Conjunctive Grammars
Tekijät: Okhotin A
Toimittaja: Alexander S. Kulikov, Gerhard J. Woeginger
Konferenssin vakiintunut nimi: International Computer Science Symposium in Russia
Kustantaja: SPRINGER INT PUBLISHING AG, GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND
Julkaisuvuosi: 2016
Kokoomateoksen nimi: Computer Science – Theory and Applications
Tietokannassa oleva lehden nimi: COMPUTER SCIENCE - THEORY AND APPLICATIONS, CSR 2016
Lehden akronyymi: LECT NOTES COMPUT SC
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 9691
Aloitussivu: 340
Lopetussivu: 351
Sivujen määrä: 12
ISBN: 978-3-319-34170-5
eISBN: 978-3-319-34171-2
ISSN: 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.
