Rational transductions and complexity of counting problems

DOI10.1007/BF01185866zbMath0833.68065OpenAlexW1991924048MaRDI 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

zbMATH Keywords

counting problemsrational transductions\(Z\)-algebraic languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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