Rational transductions and complexity of counting problems

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)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Cites Work

• 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
• 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

This page was built for publication: Rational transductions and complexity of counting problems