@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}, mrnumber = {1217682}, zbl = {0780.68082}, 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 SP - 135 EP - 148 VL - 27 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/item/ITA_1993__27_2_135_0/ LA - en ID - ITA_1993__27_2_135_0 ER -
%0 Journal Article %A Bertoni, A. %A Goldwurm, M. %T On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1993 %P 135-148 %V 27 %N 2 %I EDP-Sciences %U http://www.numdam.org/item/ITA_1993__27_2_135_0/ %G en %F ITA_1993__27_2_135_0
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, Volume 27 (1993) no. 2, pp. 135-148. http://www.numdam.org/item/ITA_1993__27_2_135_0/
1. A very hard log space counting problem, Proceedings 5th Conference on Structure in Complexity Theory, 1990, pp. 154-168. | MR
, ,2. Ranking and formal power series, Theoretical Computer Science, 79, 1991, pp. 25-35. | MR | Zbl
, and ,3. Counting problems and formal series in noncommuting variables, Inform. Process. Lett., 34, 1990, pp. 117-121. | MR | Zbl
, and ,4. The complexity of Computing the number of strings of given length in context-free languages, Theoretical Computer Science, 86, 1991, pp. 325-342. | MR | Zbl
, and ,5. Alternation, J. Assoc. Comput. Mach., 28, 1981, p. 114-133. | MR | Zbl
, and ,6. On pebble automata, Theoretical Computer Science, 44, 1986, pp. 111-121. | MR | Zbl
, , , and ,7. A taxonomy of problems with fast parallel algorithms, Information and Control, 64, 1985, pp. 2-22. | MR | Zbl
,8. Compression and ranking, Proceedings 17th ACM Symposium on Theory of Computing, 1985, pp. 59-68.
and ,9. The complexity of ranking simple languages, Math. Systems Theory, 23, 1990, pp. 1-20. | MR | Zbl
,10. Effective entropies and data compression, Information and Computation, 90, 1991, pp. 67-85. | MR | Zbl
,11. Finite automata and ambiguity, Report 253, Institut für Informationsverarbeitung, Technische Universität Graz, June 1988.
,12. The theory of Matrices, Chelsea Pub. Comp., New York 1946.
,13. Borel sets and circuits complexity, Proceedings 15th ACM Symposium on Theory of Computing, 1983, pp. 61-69.
,14. Simulation of random access machines by circuits, SIAM J. Comput, 13, 1984, pp. 409-422. | MR | Zbl
and ,15. The complexity of enumeration and reliability problems, SIAM J. Comput, 8, 1979, pp. 410-420. | MR | Zbl
,