Rational transductions and complexity of counting problems
From MaRDI portal
Publication:5096829
DOI10.1007/3-540-55808-X_16zbMath1493.68185MaRDI QIDQ5096829
Massimiliano Goldwurm, Christian Choffrut
Publication date: 18 August 2022
Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68Q70: Algebraic theory of languages and automata
Cites Work
- 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
- 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
- An efficient context-free parsing algorithm
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item