Computing a context-free grammar-generating series

Litow, Bruce (2001) Computing a context-free grammar-generating series. Information and Computation, 169 (2). pp. 174-185.

[img] PDF (Published Version) - Published Version
Restricted to Repository staff only

View at Publisher Website: http://dx.doi.org/10.1006/inco.2000.3023

Abstract

The parallel complexity of computingcontext-freegrammargeneratingseries is investigated. It is known that this problem is in DIV, but in terms of nσ rather than n, where n is the index of the desired coefficient and σ is the grammar size. A new method is presented which is in DIV in terms of 22O(σ)·n. Evidence is provided that any direct application of elimination theory to this problem leads to a space and time resource factor that is nearly exponential in grammar size.

Item ID: 13230
Item Type: Article (Refereed Research - C1)
Keywords: context-free grammar generating series
ISSN: 1090-2651
Date Deposited: 26 Jul 2012 07:16
FoR Codes: 08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080299 Computation Theory and Mathematics not elsewhere classified @ 100%
SEO Codes: 89 INFORMATION AND COMMUNICATION SERVICES > 8999 Other Information and Communication Services > 899999 Information and Communication Services not elsewhere classified @ 100%
Downloads: Total: 2
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page