{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T02:08:26Z","timestamp":1743127706118,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319948119"},{"type":"electronic","value":"9783319948126"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94812-6_25","type":"book-chapter","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T22:12:26Z","timestamp":1530223946000},"page":"299-311","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["One-Counter Automata for Parsing and Language Approximation"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Sakharov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"key":"25_CR1","volume-title":"Speech and Language Processing","author":"D Jurafsky","year":"2009","unstructured":"Jurafsky, D., Martin, J.H.: Speech and Language Processing, 2nd edn. Prentice-Hall Inc., Upper Saddle River (2009)","edition":"2"},{"issue":"1","key":"25_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/505241.505242","volume":"49","author":"L Lee","year":"2002","unstructured":"Lee, L.: Fast context-free grammar parsing requires fast boolean matrix multiplication. J. ACM 49(1), 1\u201315 (2002)","journal-title":"J. ACM"},{"issue":"1","key":"25_CR3","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1186\/1471-2105-5-71","volume":"5","author":"RD Dowell","year":"2004","unstructured":"Dowell, R.D., Eddy, S.R.: Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics 5(1), 71 (2004)","journal-title":"BMC Bioinformatics"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Petrov, S., Barrett, L., Thibaux, R., Klein, D.: Learning accurate, compact, and interpretable tree annotation. In: Proceedings of the 21st International Conference on Computational Linguistics, pp. 433\u2013440 (2006)","DOI":"10.3115\/1220175.1220230"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Klein, D., Manning, C.D.: A* parsing: fast exact Viterbi parse selection. In: Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology - Volume 1, pp. 40\u201347 (2003)","DOI":"10.3115\/1073445.1073461"},{"key":"25_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_3","volume-title":"Handbook of Formal Languages","author":"J Autebert","year":"1997","unstructured":"Autebert, J., Berstel, J., Boasson, L.: Context-free languages and push-down automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-642-59136-5_3"},{"issue":"2","key":"25_CR7","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/s10703-011-0111-7","volume":"38","author":"A Bouajjani","year":"2011","unstructured":"Bouajjani, A., Bozga, M., Habermehl, P., Iosif, R., Moro, P., Vojnar, T.: Programs with lists are counter automata. Formal Methods Syst. Des. 38(2), 158\u2013192 (2011)","journal-title":"Formal Methods Syst. Des."},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Chitic, C., Rosu, D.: On validation of XML streams using finite state machines. In: Proceedings of the 7th International Workshop on the Web and Databases, pp. 85\u201390 (2004)","DOI":"10.1145\/1017074.1017096"},{"key":"25_CR9","doi-asserted-by":"publisher","first-page":"863","DOI":"10.1137\/1.9781611973075.70","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms","author":"T. Br\u00e1zdil","year":"2010","unstructured":"Br\u00e1zdil, T., Brozek, V., Etessami, K., Kucera, A., Wojtczak, D.: One-counter Markov decision processes. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 863\u2013874 (2010)"},{"key":"25_CR10","unstructured":"Br\u00e1zdil, T., Brozek, V., Etessami, K.: One-counter stochastic games. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 108\u2013119 (2010)"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Etessami, K., Wojtczak, D., Yannakakis, M.: Quasi-birth-death processes, tree-like QBDs, probabilistic 1-counter automata, and pushdown systems. In: 5th International Conference on the Quantitative Evaluation of Systems, pp. 243\u2013253 (2008)","DOI":"10.1109\/QEST.2008.35"},{"key":"25_CR12","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(78)90020-8","volume":"7","author":"SA Greibach","year":"1978","unstructured":"Greibach, S.A.: Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7, 311\u2013324 (1978)","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/978-3-663-09367-1_2","volume-title":"Transductions and Context-Free Languages","author":"Jean Berstel","year":"1979","unstructured":"Berstel, J.: Transductions and Context-Free Languages. Leitf\u00e4den der angewandten Mathematik und Mechanik. Teubner (1979)"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"Czerwinski, W., Lasota, S.: Regular separability of one counter automata. In: 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, pp. 1\u201312 (2017)","DOI":"10.1109\/LICS.2017.8005079"},{"key":"25_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/978-3-540-88282-4_42","volume-title":"Language and Automata Theory and Applications","author":"E Render","year":"2008","unstructured":"Render, E., Kambites, M.: Polycyclic and bicyclic valence automata. In: Mart\u00edn-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 464\u2013475. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-88282-4_42"},{"issue":"1","key":"25_CR16","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(88)90009-6","volume":"58","author":"FJ Brandenburg","year":"1988","unstructured":"Brandenburg, F.J.: On the intersection of stacks and queues. Theoret. Comput. Sci. 58(1), 69\u201380 (1988)","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR17","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-94-015-9719-7_6","volume-title":"Robustness in Language and Speech Technology. Text, Speech and Language Technology","author":"M Mohri","year":"2001","unstructured":"Mohri, M., Nederhof, M.J.: Regular approximation of context-free grammars through transformation. In: Junqua, J.C., van Noord, G. (eds.) Robustness in Language and Speech Technology. Text, Speech and Language Technology, pp. 153\u2013163. Springer, Dordrecht (2001). https:\/\/doi.org\/10.1007\/978-94-015-9719-7_6"},{"key":"25_CR18","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-02737-6_16","volume-title":"Developments in Language Theory","author":"\u00d6mer E\u011fecio\u011flu","year":"2009","unstructured":"E\u011fecio\u011flu, \u00d6.: Strongly regular grammars and regular approximation of context-free languages. In: Developments in Language Theory: 13th International Conference, pp. 207\u2013220 (2009)"},{"key":"25_CR19","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.ipl.2018.03.005","volume":"135","author":"A Sakharov","year":"2018","unstructured":"Sakharov, A., Sakharov, T.: The Viterbi algorithm for subsets of stochastic context-free languages. Inf. Process. Lett. 135, 68\u201372 (2018)","journal-title":"Inf. Process. Lett."},{"key":"25_CR20","volume-title":"Mastering Regular Expressions","author":"JEF Friedl","year":"2002","unstructured":"Friedl, J.E.F.: Mastering Regular Expressions. O\u2019Reilly & Associates Inc., Sebastopol (2002)"},{"issue":"4","key":"25_CR21","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1006\/jcss.2001.1748","volume":"62","author":"J Hromkovi\u010d","year":"2001","unstructured":"Hromkovi\u010d, J., Seibert, S., Wilke, T.: Translating regular expressions into small $$\\epsilon $$-free nondeterministic finite automata. J. Comput. Syst. Sci. 62(4), 565\u2013588 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR22","unstructured":"Cotter, A., Gupta, M.R., Pfeifer, J.: A light touch for heavily constrained SGD. In: Proceedings of the 29th Conference on Learning Theory, pp. 729\u2013771 (2016)"},{"key":"25_CR23","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/978-3-319-10882-7_14","volume-title":"Theoretical Aspects of Computing \u2013 ICTAC 2014","author":"Niels Bj\u00f8rn Bugge Grathwohl","year":"2014","unstructured":"Grathwohl, N.B.B., Henglein, F., Rasmussen, U.T.: Optimally streaming greedy regular expression parsing. In: International Conference on Theoretical Aspects of Computing, pp. 224\u2013240 (2014)"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"Nederhof, M.J.: Context-free parsing through regular approximation. In: Proceedings of the International Workshop on Finite State Methods in Natural Language Processing, pp. 13\u201324 (1998)","DOI":"10.3115\/1611533.1611535"},{"issue":"2","key":"25_CR25","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1162\/0891201054223986","volume":"31","author":"MJ Nederhof","year":"2005","unstructured":"Nederhof, M.J.: A general technique to train language models on language models. Comput. Linguist. 31(2), 173\u2013186 (2005)","journal-title":"Comput. Linguist."}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94812-6_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:54:48Z","timestamp":1709826888000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-94812-6_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319948119","9783319948126"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94812-6_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"29 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Charlottetown, PE","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 July 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.smcs.upei.ca\/ciaa2018","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}