{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:44Z","timestamp":1750306724560,"version":"3.41.0"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2014,9,8]],"date-time":"2014-09-08T00:00:00Z","timestamp":1410134400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1356918"],"award-info":[{"award-number":["CCF-1356918"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000141210041, N000141310129"],"award-info":[{"award-number":["N000141210041, N000141310129"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-1353606"],"award-info":[{"award-number":["IIS-1353606"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,9,8]]},"abstract":"<jats:p>\n            A Markov sequence is a basic statistical model representing uncertain sequential data, and it is used within a plethora of applications, including speech recognition, image processing, computational biology, radio-frequency identification (RFID), and information extraction. The problem of querying a Markov sequence is studied under the conventional semantics of querying a probabilistic database, where queries are formulated as finite-state transducers. Specifically, the complexity of two main problems is analyzed. The first problem is that of computing the confidence (probability) of an answer. The second is the enumeration of the answers in the order of decreasing confidence (with the generation of the top-\n            <jats:italic>k<\/jats:italic>\n            answers as a special case), or in an approximate order thereof. In particular, it is shown that enumeration in any subexponential-approximate order is generally intractable (even for some fixed transducers), and a matching upper bound is obtained through a proposed heuristic. Due to this hardness, a special consideration is given to restricted (yet common) classes of transducers that extract matches of a regular expression (subject to prefix and suffix constraints), and it is shown that these classes are, indeed, significantly more tractable.\n          <\/jats:p>","DOI":"10.1145\/2630065","type":"journal-article","created":{"date-parts":[[2014,9,9]],"date-time":"2014-09-09T14:39:29Z","timestamp":1410273569000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Transducing Markov sequences"],"prefix":"10.1145","volume":"61","author":[{"given":"Benny","family":"Kimelfeld","sequence":"first","affiliation":[{"name":"LogicBlox, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"R\u00e9","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,9,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2002.1008386"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1562"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066277"},{"volume-title":"Proceedings of the AAAI\/IAAI Conference on Artificial Intelligence. AAAI Press \/ The MIT Press, 328--334","author":"Califf M. E.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.291449"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872823"},{"volume-title":"Proceedings of ACL. The Association for Computer Linguistics, 128--137","author":"Chiticariu L.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10032-007-0054-0"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.04.003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559831"},{"volume-title":"Proceedings of VLDB, Morgan-Kaufmann, 864--875","author":"Dalvi N. N.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265571"},{"volume-title":"Proceedings of VLDB, Morgan-Kaufmann, 588--599","author":"Deshpande A.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of CIDR. www.crdrdb.org.","author":"Diao Y.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Durbin R. Eddy S. R. Krogh A. and Mitchison G. J. 1998. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.  Durbin R. Eddy S. R. Krogh A. and Mitchison G. J. 1998. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids . Cambridge University Press.","DOI":"10.1017\/CBO9780511790492"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11424925_22"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2463665"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/83.552077"},{"key":"e_1_2_1_23_1","unstructured":"Gantz J. F. Reinsel D. Chute C. Schlichting W. McArthur J. Minton S. Xheneti I. Toncheva A. and Manfrediz A. 2007. The expanding digital universe: A forecast of worldwide information growth through 2010. http:\/\/www.emc.com\/collateral\/analyst-reports\/expanding-digital-idc-white-paper.pdf.  Gantz J. F. Reinsel D. Chute C. Schlichting W. McArthur J. Minton S. Xheneti I. Toncheva A. and Manfrediz A. 2007. The expanding digital universe: A forecast of worldwide information growth through 2010. http:\/\/www.emc.com\/collateral\/analyst-reports\/expanding-digital-idc-white-paper.pdf."},{"volume-title":"Proceedings of FOCS. IEEE Computer Society, 627--636","year":"1996","author":"H\u00e5stad J.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","unstructured":"HMMER. 2010. Biosequence analysis using hidden Markov models. http:\/\/hmmer.janelia.org\/.  HMMER. 2010. Biosequence analysis using hidden Markov models. http:\/\/hmmer.janelia.org\/."},{"key":"e_1_2_1_26_1","unstructured":"HTK. 2009. The hidden Markov toolkit. http:\/\/htk.eng.cam.ac.uk\/.  HTK. 2009. The hidden Markov toolkit. http:\/\/htk.eng.cam.ac.uk\/."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559984"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.04.011"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497525"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.229"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559894"},{"volume-title":"Proceedings of SODA. ACM\/SIAM, 551--557","author":"Kannan S.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.3115\/976909.979676"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376687"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807090"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142377"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265572"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.01.002"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376932"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514911"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.910572"},{"volume-title":"Proceedings of ICML. Morgan-Kaufmann, 282--289","author":"Lafferty J.","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","first-page":"401","article-title":"A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Manage","volume":"18","author":"Lawler E. L.","year":"1972","journal-title":"Sci."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.21"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687605"},{"volume-title":"Proceedings of VLDB. Morgan-Kaufmann, 227--238","author":"Lud\u00e4scher B.","key":"e_1_2_1_47_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656437"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.16.3.682"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1626"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.18626"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376688"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453943"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497511"},{"volume-title":"SEQ: A model for sequence databases","year":"1995","author":"Seshadri P.","key":"e_1_2_1_56_1"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.3115\/1073445.1073473"},{"volume-title":"Proceedings of NIPS. MIT Press, 1249--1256","author":"Sha F.","key":"e_1_2_1_58_1"},{"volume-title":"Proceedings of VLDB. 1033--1044","author":"Shen W.","key":"e_1_2_1_59_1"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497514"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007562322031"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221023"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.33"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"volume-title":"Proceedings of CIDR. www.crdrdb.org, 262--276","year":"2005","author":"Widom J.","key":"e_1_2_1_66_1"},{"key":"e_1_2_1_67_1","first-page":"712","article-title":"Finding the k shortest loopless paths in a network. Manage","volume":"17","author":"Yen J. Y.","year":"1971","journal-title":"Sci."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90037-2"},{"volume-title":"Proceedings of ACL (1). The Association for Computer Linguistics, 1159--1168","author":"Zhang C.","key":"e_1_2_1_69_1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2630065","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2630065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:36Z","timestamp":1750231176000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2630065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,8]]},"references-count":69,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,9,8]]}},"alternative-id":["10.1145\/2630065"],"URL":"https:\/\/doi.org\/10.1145\/2630065","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2014,9,8]]},"assertion":[{"value":"2010-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}