Counting problems and algebraic formal power series in noncommuting variables

DOI10.1016/0020-0190(90)90089-GzbMath0695.68053OpenAlexW2074415539MaRDI QIDQ910245

Paolo Massazza, Massimiliano Goldwurm, Alberto Bertoni

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90089-g

zbMATH Keywords

circuit complexityformal languagescounting problemsinteger division

Mathematics Subject Classification ID

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

Related Items

On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions ⋮ Holonomic functions and their relation to linearly constrained languages ⋮ Ranking and formal power series ⋮ Preface ⋮ Division in logspace-uniformNC¹ ⋮ Computing a context-free grammar-generating series

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analytic models and ambiguity of context-free languages
• The complexity of computing the number of strings of given length in context-free languages
• Formal languages and enumeration
• Algebraic languages and polyominoes enumeration
• Planar Maps are Well Labeled Trees
• A taxonomy of problems with fast parallel algorithms
• Logarithmic Depth Circuits for Algebraic Functions
• Log Depth Circuits for Division and Related Problems
• The Complexity of Enumeration and Reliability Problems