Rational transductions and complexity of counting problems
From MaRDI portal
Publication:4850332
DOI10.1007/BF01185866zbMath0833.68065MaRDI QIDQ4850332
Massimiliano Goldwurm, Christian Choffrut
Publication date: 14 November 1995
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01185866
68Q25: Analysis of algorithms and problem complexity
Related Items
From Combinatorial Games to Shape-Symmetric Morphisms, Numeration systems on a regular language: Arithmetic operations, recognizability and formal power series
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Effective entropies and data compression
- Analytic models and ambiguity of context-free languages
- The complexity of computing the number of strings of given length in context-free languages
- A very hard log-space counting class
- A homomorphism theorem for weighted context-free grammars
- Optimization of LR(k) parsers
- Ranking and formal power series
- The complexity of ranking simple languages
- A taxonomy of problems with fast parallel algorithms
- The Complexity of Enumeration and Reliability Problems
- Compression and Ranking
- The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages
- An efficient context-free parsing algorithm