The complexity of computing the number of strings of given length in context-free languages
From MaRDI portal
Publication:1178713
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)
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Distributed algorithms (68W15)
Related Items
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
