Computing a context-free grammar-generating series

DOI10.1006/inco.2000.3023zbMath1007.68085OpenAlexW2070190750MaRDI QIDQ1854451

Bruce Litow

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2000.3023

zbMATH Keywords

parallel complexitycomputing context-free grammar-generating series

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Grammars and rewriting systems (68Q42)

Related Items

Division in logspace-uniformNC¹

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Effective entropies and data compression
• Counting problems and algebraic formal power series in noncommuting variables
• Analytic models and ambiguity of context-free languages
• On uniform circuit complexity
• On iterated integer product
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Algebraic functions over finite fields
• Optimization of LR(k) parsers
• The complexity of ranking simple languages
• A taxonomy of problems with fast parallel algorithms
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• Logarithmic Depth Circuits for Algebraic Functions
• Log Depth Circuits for Division and Related Problems
• On Relating Time and Space to Size and Depth
• Recognition and parsing of context-free languages in time n3
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers