On ranking 1-way finitely ambiguous NL languages and \# P₁-complete census functions

DOI10.1051/ITA/1993270201351MaRDI QIDQ5286060zbMATH OpenOpenAlexFDO

Authors Massimiliano Goldwurm, Alberto Bertoni

Publication date 29 June 1993

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92442

zbMATH Keywords

counting problemdirect sum over matricesKronecker productTurin machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• The complexity of ranking simple languages
• Ranking and formal power series
• On languages accepted with simultaneous complexity bounds and their ranking problem
• scientific article; zbMATH DE number 4041256
• Comparing counting classes for logspace, one-way logspace, and first-order

Cites work

• A taxonomy of problems with fast parallel algorithms
• Alternation
• Counting problems and algebraic formal power series in noncommuting variables
• Effective entropies and data compression
• scientific article; zbMATH DE number 3009965 (Why is no real title available?)
• On pebble automata
• Ranking and formal power series
• Simulation of Parallel Random Access Machines by Circuits
• The complexity of computing the number of strings of given length in context-free languages
• The Complexity of Enumeration and Reliability Problems
• The complexity of ranking simple languages

Cited in

(5)

• Theory of traces
• The complexity of ranking simple languages
• Comparing counting classes for logspace, one-way logspace, and first-order
• On languages accepted with simultaneous complexity bounds and their ranking problem
• Preface

This page was built for publication: On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions

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