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]](https://researchonline.jcu.edu.au/style/images/fileicons/application_pdf.png) |
PDF (Published Version)
- Published Version
Restricted to Repository staff only |
View at Publisher Website: http://dx.doi.org/10.1006/inco.2000.3023
6
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 (Research - C1) |
| ISSN: | 1090-2651 |
| 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% |
| Downloads: |
Total: 6 |
| More Statistics |
Actions (Repository Staff Only)
 |
Item Control Page |