{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T19:37:30Z","timestamp":1703187450376},"reference-count":15,"publisher":"EDP Sciences","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[1993]]},"DOI":"10.1051\/ita\/1993270201351","type":"journal-article","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T15:08:00Z","timestamp":1486048080000},"page":"135-148","source":"Crossref","is-referenced-by-count":2,"title":["On ranking 1-way finitely ambiguous NL languages and $\\# P_1$-complete census functions"],"prefix":"10.1051","volume":"27","author":[{"given":"A.","family":"Bertoni","sequence":"first","affiliation":[]},{"given":"M.","family":"Goldwurm","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2011,1,8]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"1. ALVAREZ C., JENNER B., A very hard log space counting problem, Proceedings 5th Conference on Structure in Complexity Theory, 1990, pp. 154-168.1097666","DOI":"10.1109\/SCT.1990.113964"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"2. BERTONI A., BRUSCHI D. and GOLDWURM M., Ranking and formal power series, Theoretical Computer Science, 79, 1991, pp. 25-35.11029500721.68023","DOI":"10.1016\/0304-3975(91)90144-Q"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"3. BERTONI A., GOLDWURM M. and MASSAZZA P., Counting problems and formal series in noncommuting variables, Inform. Process. Lett., 34, 1990, pp. 117-121.10599750695.68053","DOI":"10.1016\/0020-0190(90)90089-G"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"4. BERTONI A., GOLDWURM M. and SABADINI N., The complexity of Computing the number of strings of given length in context-free languages, Theoretical Computer Science, 86, 1991, pp. 325-342.11227930744.68066","DOI":"10.1016\/0304-3975(91)90023-U"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"5. CHANDRA A., KOZEN D. and STOCKMEYER L., Alternation, J. Assoc. Comput. Mach., 28, 1981, p. 114-133.6031860473.68043","DOI":"10.1145\/322234.322243"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"6. CHANG J. H., IBARRA O. H., PALIS M. A., and RAVIKUMAR B., On pebble automata, Theoretical Computer Science, 44, 1986, pp. 111-121.8586930612.68045","DOI":"10.1016\/0304-3975(86)90112-X"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"7. COOK S., A taxonomy of problems with fast parallel algorithms, Information and Control, 64, 1985, pp. 2-22.8370880575.68045","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"8. GOLDBERG A. V. and SIPSER M., Compression and ranking, Proceedings 17th ACM Symposium on Theory of Computing, 1985, pp. 59-68.","DOI":"10.1145\/22145.22194"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"9. HUYNH D. T., The complexity of ranking simple languages, Math. Systems Theory, 23, 1990, pp. 1-20.10282300692.68059","DOI":"10.1007\/BF02090763"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"10. HUYNH D. T., Effective entropies and data compression, Information and Computation, 90, 1991, pp. 67-85.10888060715.68047","DOI":"10.1016\/0890-5401(91)90060-F"},{"key":"R11","unstructured":"11. KUICH W., Finite automata and ambiguity, Report 253, Institut f\u00fcr Informationsverarbeitung, Technische Universit\u00e4t Graz, June 1988."},{"key":"R12","unstructured":"12. MACDUFFEE C. C., The theory of Matrices, Chelsea Pub. Comp., New York 1946.0007.19507"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"13. SIPSER M., Borel sets and circuits complexity, Proceedings 15th ACM Symposium on Theory of Computing, 1983, pp. 61-69.","DOI":"10.1145\/800061.808733"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"14. STOCKMEYER L. and VISHKIN U., Simulation of random access machines by circuits, SIAM J. Comput, 13, 1984, pp. 409-422.7399970533.68048","DOI":"10.1137\/0213027"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"15. VALIANT L. G., The complexity of enumeration and reliability problems, SIAM J. Comput, 8, 1979, pp. 410-420.5392580419.68082","DOI":"10.1137\/0208032"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1993270201351\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T05:59:02Z","timestamp":1568786342000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1993270201351"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"references-count":15,"journal-issue":{"issue":"2"},"alternative-id":["ita1993270201351"],"URL":"https:\/\/doi.org\/10.1051\/ita\/1993270201351","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993]]}}}