Hardest languages for conjunctive and Boolean grammars

Результат исследований: Научные публикации в периодических изданияхстатьярецензирование

2 Цитирования (Scopus)

Аннотация

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 its 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, as well as for Boolean grammars, which are further equipped with a negation operator. At the same time, it is shown that no such characterization is possible for several subclasses of linear grammars.

Язык оригиналаанглийский
Страницы (с-по)1-18
Число страниц18
ЖурналInformation and Computation
Том266
DOI
СостояниеОпубликовано - 1 июн 2019

Предметные области Scopus

  • Теоретические компьютерные науки
  • Информационные системы
  • Прикладные компьютерные науки
  • Математика и теория расчета

Fingerprint Подробные сведения о темах исследования «Hardest languages for conjunctive and Boolean grammars». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать