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

DOI10.1051/ITA/1993270201351zbMATH Open0780.68082OpenAlexW17036322MaRDI QIDQ5286060FDOQ5286060

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

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

zbMATH Keywords

Kronecker productcounting problemdirect sum over matricesTurin machines

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• The complexity of ranking simple languages
• Theory of traces
• 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)