On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions

DOI10.1051/ita/1993270201351zbMath0780.68082OpenAlexW17036322MaRDI QIDQ5286060

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

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)

Related Items

Theory of traces ⋮ On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ Preface

Cites Work

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