A4 Refereed article in a conference publication
The Hardest Language for Conjunctive Grammars
Authors: Okhotin A
Editors: Alexander S. Kulikov, Gerhard J. Woeginger
Conference name: International Computer Science Symposium in Russia
Publisher: SPRINGER INT PUBLISHING AG, GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND
Publication year: 2016
Book title : Computer Science – Theory and Applications
Journal name in source: COMPUTER SCIENCE - THEORY AND APPLICATIONS, CSR 2016
Journal acronym: LECT NOTES COMPUT SC
Series title: Lecture Notes in Computer Science
Volume: 9691
First page : 340
Last page: 351
Number of pages: 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(external)
Abstract
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.
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.
UTU Research Portal