On ranking 1-way finitely ambiguous NL languages and #P 1 -complete census functions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) no. 2, pp. 135-148.
@article{ITA_1993__27_2_135_0,
     author = {Bertoni, A. and Goldwurm, M.},
     title = {On ranking 1-way finitely ambiguous {NL} languages and $\# P_1$-complete census functions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {135--148},
     publisher = {EDP-Sciences},
     volume = {27},
     number = {2},
     year = {1993},
     zbl = {0780.68082},
     mrnumber = {1217682},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1993__27_2_135_0/}
}
TY  - JOUR
AU  - Bertoni, A.
AU  - Goldwurm, M.
TI  - On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1993
DA  - 1993///
SP  - 135
EP  - 148
VL  - 27
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1993__27_2_135_0/
UR  - https://zbmath.org/?q=an%3A0780.68082
UR  - https://www.ams.org/mathscinet-getitem?mr=1217682
LA  - en
ID  - ITA_1993__27_2_135_0
ER  - 
Bertoni, A.; Goldwurm, M. On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) no. 2, pp. 135-148. http://www.numdam.org/item/ITA_1993__27_2_135_0/

1. C. Alvarez, B. Jenner, A very hard log space counting problem, Proceedings 5th Conference on Structure in Complexity Theory, 1990, pp. 154-168. | MR 1097666

2. A. Bertoni, D. Bruschi and M. Goldwurm, Ranking and formal power series, Theoretical Computer Science, 79, 1991, pp. 25-35. | MR 1102950 | Zbl 0721.68023

3. A. Bertoni, M. Goldwurm and P. Massazza, Counting problems and formal series in noncommuting variables, Inform. Process. Lett., 34, 1990, pp. 117-121. | MR 1059975 | Zbl 0695.68053

4. A. Bertoni, M. Goldwurm and N. Sabadini, The complexity of Computing the number of strings of given length in context-free languages, Theoretical Computer Science, 86, 1991, pp. 325-342. | MR 1122793 | Zbl 0744.68066

5. A. Chandra, D. Kozen and L. Stockmeyer, Alternation, J. Assoc. Comput. Mach., 28, 1981, p. 114-133. | MR 603186 | Zbl 0473.68043

6. J. H. Chang, O. H. Ibarra, M. A. Palis, and B. Ravikumar, On pebble automata, Theoretical Computer Science, 44, 1986, pp. 111-121. | MR 858693 | Zbl 0612.68045

7. S. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control, 64, 1985, pp. 2-22. | MR 837088 | Zbl 0575.68045

8. A. V. Goldberg and M. Sipser, Compression and ranking, Proceedings 17th ACM Symposium on Theory of Computing, 1985, pp. 59-68.

9. D. T. Huynh, The complexity of ranking simple languages, Math. Systems Theory, 23, 1990, pp. 1-20. | MR 1028230 | Zbl 0692.68059

10. D. T. Huynh, Effective entropies and data compression, Information and Computation, 90, 1991, pp. 67-85. | MR 1088806 | Zbl 0715.68047

11. W. Kuich, Finite automata and ambiguity, Report 253, Institut für Informationsverarbeitung, Technische Universität Graz, June 1988.

12. C. C. Macduffee, The theory of Matrices, Chelsea Pub. Comp., New York 1946.

13. M. Sipser, Borel sets and circuits complexity, Proceedings 15th ACM Symposium on Theory of Computing, 1983, pp. 61-69.

14. L. Stockmeyer and U. Vishkin, Simulation of random access machines by circuits, SIAM J. Comput, 13, 1984, pp. 409-422. | MR 739997 | Zbl 0533.68048

15. L. G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput, 8, 1979, pp. 410-420. | MR 539258 | Zbl 0419.68082