Rational transductions and complexity of counting problems

DOI10.1007/3-540-55808-X_16MaRDI QIDQ5096829zbMATH OpenFDO

Authors Massimiliano Goldwurm, Christian Choffrut

Publication date 18 August 2022

Published in Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55808-X_16

Mathematics Subject Classification ID

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

Recommendations

• Rational transductions and complexity of counting problems
• Counting problems and algebraic formal power series in noncommuting variables
• Ranking and formal power series
• scientific article; zbMATH DE number 45433
• Combinatorial Complexity of Regular Languages

Cites work

• A homomorphism theorem for weighted context-free grammars
• A taxonomy of problems with fast parallel algorithms
• A very hard log-space counting class
• An efficient context-free parsing algorithm
• Analytic models and ambiguity of context-free languages
• Effective entropies and data compression
• scientific article; zbMATH DE number 3817043 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• Ranking and formal power series
• The complexity of computing the number of strings of given length in context-free languages
• The Complexity of Enumeration and Reliability Problems
• The complexity of ranking simple languages

Cited in

(5)

• The complexity of ranking simple languages
• scientific article; zbMATH DE number 4211520 (Why is no real title available?)
• Iteration of rational transductions
• Rational transductions and complexity of counting problems
• Counting problems and algebraic formal power series in noncommuting variables

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096829)