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

A. Bertoni; M. Goldwurm

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1993)

  • Volume: 27, Issue: 2, page 135-148
  • ISSN: 0988-3754

How to cite

top

Bertoni, A., and 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 27.2 (1993): 135-148. <http://eudml.org/doc/92442>.

@article{Bertoni1993,
author = {Bertoni, A., Goldwurm, M.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {Turin machines; Kronecker product; direct sum over matrices; counting problem},
language = {eng},
number = {2},
pages = {135-148},
publisher = {EDP-Sciences},
title = {On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions},
url = {http://eudml.org/doc/92442},
volume = {27},
year = {1993},
}

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
PB - EDP-Sciences
VL - 27
IS - 2
SP - 135
EP - 148
LA - eng
KW - Turin machines; Kronecker product; direct sum over matrices; counting problem
UR - http://eudml.org/doc/92442
ER -

References

top
  1. 1. C. ALVAREZ, B. JENNER, A very hard log space counting problem, Proceedings 5th Conference on Structure in Complexity Theory, 1990, pp. 154-168. MR1097666
  2. 2. A. BERTONI, D. BRUSCHI and M. GOLDWURM, Ranking and formal power series, Theoretical Computer Science, 79, 1991, pp. 25-35. Zbl0721.68023MR1102950
  3. 3. A. BERTONI, M. GOLDWURM and P. MASSAZZA, Counting problems and formal series in noncommuting variables, Inform. Process. Lett., 34, 1990, pp. 117-121. Zbl0695.68053MR1059975
  4. 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. Zbl0744.68066MR1122793
  5. 5. A. CHANDRA, D. KOZEN and L. STOCKMEYER, Alternation, J. Assoc. Comput. Mach., 28, 1981, p. 114-133. Zbl0473.68043MR603186
  6. 6. J. H. CHANG, O. H. IBARRA, M. A. PALIS, and B. RAVIKUMAR, On pebble automata, Theoretical Computer Science, 44, 1986, pp. 111-121. Zbl0612.68045MR858693
  7. 7. S. COOK, A taxonomy of problems with fast parallel algorithms, Information and Control, 64, 1985, pp. 2-22. Zbl0575.68045MR837088
  8. 8. A. V. GOLDBERG and M. SIPSER, Compression and ranking, Proceedings 17th ACM Symposium on Theory of Computing, 1985, pp. 59-68. 
  9. 9. D. T. HUYNH, The complexity of ranking simple languages, Math. Systems Theory, 23, 1990, pp. 1-20. Zbl0692.68059MR1028230
  10. 10. D. T. HUYNH, Effective entropies and data compression, Information and Computation, 90, 1991, pp. 67-85. Zbl0715.68047MR1088806
  11. 11. W. KUICH, Finite automata and ambiguity, Report 253, Institut für Informationsverarbeitung, Technische Universität Graz, June 1988. 
  12. 12. C. C. MACDUFFEE, The theory of Matrices, Chelsea Pub. Comp., New York 1946. Zbl0007.19507
  13. 13. M. SIPSER, Borel sets and circuits complexity, Proceedings 15th ACM Symposium on Theory of Computing, 1983, pp. 61-69. 
  14. 14. L. STOCKMEYER and U. VISHKIN, Simulation of random access machines by circuits, SIAM J. Comput, 13, 1984, pp. 409-422. Zbl0533.68048MR739997
  15. 15. L. G. VALIANT, The complexity of enumeration and reliability problems, SIAM J. Comput, 8, 1979, pp. 410-420. Zbl0419.68082MR539258

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.