Counting problems and algebraic formal power series in noncommuting variables

DOI10.1016/0020-0190(90)90089-GMaRDI QIDQ910245zbMATHOpenAlexFDO

Authors Alberto Bertoni, Massimiliano Goldwurm, P. Massazza

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

formal languagescircuit complexitycounting problemsinteger division

Mathematics Subject Classification ID

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

Recommendations

• Ranking and formal power series
• scientific article; zbMATH DE number 4033108
• The complexity of computing the number of strings of given length in context-free languages
• Rational transductions and complexity of counting problems
• Rational transductions and complexity of counting problems

Cites work

• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 4033108 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• Algebraic languages and polyominoes enumeration
• Analytic models and ambiguity of context-free languages
• Formal languages and enumeration
• Log Depth Circuits for Division and Related Problems
• Logarithmic Depth Circuits for Algebraic Functions
• Planar Maps are Well Labeled Trees
• The Complexity of Enumeration and Reliability Problems
• The complexity of computing the number of strings of given length in context-free languages

Cited in

(11)

• scientific article; zbMATH DE number 49785 (Why is no real title available?)
• On meta-normal forms for algebraic power series in noncommuting variables
• scientific article; zbMATH DE number 2051169 (Why is no real title available?)
• On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
• Division in logspace-uniform NC
• Bounded length UCFG equivalence
• Computing a context-free grammar-generating series
• Ranking and formal power series
• Holonomic functions and their relation to linearly constrained languages
• Rational transductions and complexity of counting problems
• Preface

This page was built for publication: Counting problems and algebraic formal power series in noncommuting variables

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