• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Inverse Homomorphic Characterizations of Conjunctive and Boolean Grammars

Alexander Okhotin, Inverse Homomorphic Characterizations of Conjunctive and Boolean Grammars. TUCS Technical Reports 1080, TUCS, 2013.

Abstract:

A well-known theorem by Greibach ("The hardest context-free language", SIAM J. Comp., 1973) states that there exists such a "hardest" context-free language L_0, that every context-free language over any alphabet is representable as an inverse homomorphic image h^{-1}(L_0), for a suitable homomorphism h. This paper establishes similar characterizations for conjunctive grammars and for Boolean grammars, that is, for context-free grammars extended with conjunction and negation operators.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tOkhotin_Alexander13a,
  title = {Inverse Homomorphic Characterizations of Conjunctive and Boolean Grammars},
  author = {Okhotin, Alexander},
  number = {1080},
  series = {TUCS Technical Reports},
  publisher = {TUCS},
  year = {2013},
  keywords = {Conjunctive grammars, Boolean grammars, homomorphisms, hardest language},
  ISBN = {978-952-12-2903-9},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication