A4 Refereed article in a conference publication

The Hardest Language for Conjunctive Grammars




AuthorsOkhotin A

EditorsAlexander S. Kulikov, Gerhard J. Woeginger

Conference nameInternational Computer Science Symposium in Russia

PublisherSPRINGER INT PUBLISHING AG, GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND

Publication year2016

Book title Computer Science – Theory and Applications

Journal name in sourceCOMPUTER SCIENCE - THEORY AND APPLICATIONS, CSR 2016

Journal acronymLECT NOTES COMPUT SC

Series titleLecture Notes in Computer Science

Volume9691

First page 340

Last page351

Number of pages12

ISBN978-3-319-34170-5

eISBN978-3-319-34171-2

ISSN0302-9743

DOIhttps://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.



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