The complexity of computing the number of strings of given length in context-free languages

DOI10.1016/0304-3975(91)90023-UzbMath0744.68066MaRDI QIDQ1178713

Alberto Bertoni, Nicoletta Sabadini, Massimiliano Goldwurm

Publication date: 26 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

counting functioncontext-free languagescounting Turing machine

Mathematics Subject Classification ID

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

Related Items (10)

On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions ⋮ Generating, sampling and counting subclasses of regular tree languages ⋮ Rational transductions and complexity of counting problems ⋮ Rational transductions and complexity of counting problems ⋮ Counting problems and algebraic formal power series in noncommuting variables ⋮ Preface ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Some Applications of the Schutzenberger-Bertoni Method ⋮ Counting problems for parikh images ⋮ The complexity of computing maximal word functions

Cites Work

• The complexity of computing the permanent
• On computing the determinant in small parallel time using a small number of processors
• Analytic models and ambiguity of context-free languages
• On uniform circuit complexity
• Towards a complexity theory of synchronous parallel computation
• Formal languages and enumeration
• Algebraic languages and polyominoes enumeration
• Calcul pratique des coefficients de Taylor d'une fonction algébrique
• A contect-free language and enumeration problems on infinite trees and digraphs
• Fast multiplication of large numbers
• Enumeration des graphes planaires à l'aide des séries formelles en variables non commutatives
• Planar Maps are Well Labeled Trees
• A taxonomy of problems with fast parallel algorithms
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Logarithmic Depth Circuits for Algebraic Functions
• Log Depth Circuits for Division and Related Problems
• The Complexity of Enumeration and Reliability Problems
• The characterization of nonexpansive grammars by rational power series
• On Relating Time and Space to Size and Depth
• On context-free languages and push-down automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of computing the number of strings of given length in context-free languages