Parsing Boolean grammars over a one-letter alphabet using online convolution

Alexander Okhotin, Christian Reitwießner

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

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

Аннотация

Consider context-free grammars generating strings over a one-letter alphabet. For the membership problem for such grammars, stated as "Given a grammar G and a string an, determine whether an is generated by G", only a nave O(|G|·n2)-time algorithm is known. This paper develops a new algorithm solving this problem, which is based upon fast multiplication of integers, works in time |G|·nlog3n·2O(log*n), and is applicable to context-free grammars augmented with Boolean operations, known as Boolean grammars. For unambiguous grammars, the running time of the algorithm is reduced to |G|·nlog2n·2O(log*n). The algorithm is based upon (a simplification of) the online integer multiplication algorithm by Fischer and Stockmeyer [M.J. Fischer, L.J. Stockmeyer, Fast on-line integer multiplication, Journal of Computer and System Sciences 9 (3) (1974) 317331].

Язык оригиналаанглийский
Страницы (с-по)149-157
Число страниц9
ЖурналTheoretical Computer Science
Том457
DOI
СостояниеОпубликовано - 26 окт 2012

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

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Parsing Boolean grammars over a one-letter alphabet using online convolution». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать