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.
PDF (Published Version)
- Published Version
Restricted to Repository staff only
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 Type:||Article (Refereed Research - C1)|
|Keywords:||context-free grammar generating series|
|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%|