{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T06:28:13Z","timestamp":1648535293533},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2009,11]]},"DOI":"10.1007\/s00236-009-0104-9","type":"journal-article","created":{"date-parts":[[2009,8,31]],"date-time":"2009-08-31T06:42:29Z","timestamp":1251700949000},"page":"533-547","source":"Crossref","is-referenced-by-count":7,"title":["On regular tree languages and deterministic pushdown automata"],"prefix":"10.1007","volume":"46","author":[{"given":"Jan","family":"Janou\u0161ek","sequence":"first","affiliation":[]},{"given":"Bo\u0159ivoj","family":"Melichar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,9,1]]},"reference":[{"key":"104_CR1","volume-title":"The Theory of Parsing, Translation and Compiling, vol. 1: Parsing, vol. 2: Compiling","author":"A.V. Aho","year":"1972","unstructured":"Aho A.V., Ullman J.D.: The Theory of Parsing, Translation and Compiling, vol. 1: Parsing, vol. 2: Compiling. Prentice Hall, New York (1972)"},{"key":"104_CR2","volume-title":"Compilers: Principles, Techniques, and Tools","author":"A.V. Aho","year":"1986","unstructured":"Aho A.V., Sethi R., Ullman J.D.: Compilers: Principles, Techniques, and Tools. Addison Wesley, Reading, Mass (1986)"},{"key":"104_CR3","volume-title":"Attribute Grammars, Applications and Systems. LNCS 545","year":"1991","unstructured":"Alblas, H., Melichar, B. (eds): Attribute Grammars, Applications and Systems. LNCS 545. Springer, Berlin (1991)"},{"key":"104_CR4","doi-asserted-by":"crossref","unstructured":"Alur, R.: Marrying words and trees. In: 26th ACM symposium on principles of database systems, pp. 233\u2013242. ACM, New York (2007)","DOI":"10.1145\/1265530.1265564"},{"key":"104_CR5","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: 36th ACM symposium on theory of computing, pp. 202\u2013211. ACM, New York (2004)","DOI":"10.1145\/1007352.1007390"},{"key":"104_CR6","unstructured":"Arbology www pages: Available on: http:\/\/www.arbology.org . Aug (2009)"},{"issue":"9","key":"104_CR7","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1007\/PL00013319","volume":"37","author":"J. Aycock","year":"2001","unstructured":"Aycock J., Horspool N., Janou\u0161ek J., Melichar B.: Even faster generalized LR parsing. Acta Inform. 37(9), 633\u2013651 (2001)","journal-title":"Acta Inform."},{"key":"104_CR8","unstructured":"Bison-GNU parser generator: Available on: http:\/\/www.gnu.org\/software\/bison\/ . May (2008)"},{"key":"104_CR9","doi-asserted-by":"crossref","unstructured":"Chase, D.: An improvement to bottom up tree pattern matching. In: Proceedings of 14th annual ACM symposium on principles of programming languages, pp. 168\u2013177 (1987)","DOI":"10.1145\/41625.41640"},{"key":"104_CR10","unstructured":"Cleophas, L.: Tree algorithms. Two taxonomies and a toolkit. Ph.D. thesis, Technische Universiteit Eindhoven, Eindhoven (2008)"},{"key":"104_CR11","unstructured":"Comon, H., Dauchet, M., Gilleron, R., L\u00f6ding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications. Available on: http:\/\/www.grappa.univ-lille3.fr\/tata (2007). Release 12 Oct 2007"},{"key":"104_CR12","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Hancart, Ch.: Automata for matching patterns. In: Linear Modeling: Backgroung and Application. Handbook of Formal Languages, vol. 2, pp. 399\u2013462. Springer, Berlin, Heidelberg (1997)","DOI":"10.1007\/978-3-662-07675-0_9"},{"key":"104_CR13","volume-title":"Jewels of Stringology","author":"M. Crochemore","year":"1994","unstructured":"Crochemore M., Rytter W.: Jewels of Stringology. World Scientific, New Jersey (1994)"},{"key":"104_CR14","volume-title":"Attribute Grammars and Their Applications. LNCS 461","year":"1990","unstructured":"Deransart, P., Jourdan, M. (eds): Attribute Grammars and Their Applications. LNCS 461. Springer, Berlin (1990)"},{"key":"104_CR15","unstructured":"Engelfriet, J.: Tree Automata and Tree Grammars. Lecture Notes. DAIMI FN-IO, University of Aarhus, Denmark (1975)"},{"issue":"8","key":"104_CR16","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1007\/BF01178733","volume":"31","author":"Ch. Ferdinand","year":"1994","unstructured":"Ferdinand Ch., Seidl H., Wilhelm R.: Tree automata for code selection. Acta Inform. 31(8), 741\u2013760 (1994)","journal-title":"Acta Inform."},{"key":"104_CR17","doi-asserted-by":"crossref","unstructured":"Fleuri, T., Janou\u0161ek, J., Melichar, B.: Subtree matching by deterministic pushdown automata. In: Proceedings of WAPL\u201909 Conference, Mragowo (2009)","DOI":"10.1109\/IMCSIT.2009.5352769"},{"key":"104_CR18","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/151640.151642","volume":"1, 3","author":"Ch.W. Fraser","year":"1992","unstructured":"Fraser Ch.W., Hanson D.A., Proebsting T.A.: Engineering a simple, efficient code generator generator. ACM Lett. Program. Lang. Sys. 1, 3, 213\u2013226 (1992)","journal-title":"ACM Lett. Program. Lang. Sys."},{"key":"104_CR19","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/131080.131089","volume":"27","author":"Ch.W. Fraser","year":"1992","unstructured":"Fraser Ch.W., Henry R.R., Proebsting T.A.: BURG: fast optimal instruction selection and tree parsing. ACM SIGPLAN Notices 27, 68\u201376 (1992)","journal-title":"ACM SIGPLAN Notices"},{"key":"104_CR20","volume-title":"Tree Automata","author":"F. Gecseg","year":"1984","unstructured":"Gecseg F.: Tree Automata. Akademiai Kiado, Budapest (1984)"},{"key":"104_CR21","doi-asserted-by":"crossref","unstructured":"Gecseg, F., Steinby, M.: Tree languages. In: Beyond Words. Handbook of Formal Languages, vol. 3, pp. 1\u201368. Springer, Berlin, Heidelberg (1997)","DOI":"10.1007\/978-3-642-59126-6_1"},{"key":"104_CR22","doi-asserted-by":"crossref","unstructured":"Glanville, R.S., Graham, S.L.: A new approach to compiler code generation. In: Proceedings of 5th ACM Symposium on Principles of Programming Languages, pp. 231\u2013240 (1978)","DOI":"10.1145\/512760.512785"},{"issue":"1","key":"104_CR23","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0167-6423(89)90015-4","volume":"13","author":"C. Hemerik","year":"1989","unstructured":"Hemerik C., Katoen J.P.: Bottom-up tree acceptors. Sci. Comput. Program. 13(1), 51\u201372 (1989)","journal-title":"Sci. Comput. Program."},{"issue":"1","key":"104_CR24","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/322290.322295","volume":"29","author":"C.M. Hoffmann","year":"1982","unstructured":"Hoffmann C.M., O\u2019Donnell M.J.: Pattern matching in trees. J. ACM 29(1), 68\u201395 (1982)","journal-title":"J. ACM"},{"key":"104_CR25","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"2001","unstructured":"Hopcroft J.E., Motwani R., Ullman J.D.: Introduction to Automata Theory, Languages, and Computation. 2nd edn. Addison-Wesley, New York (2001)","edition":"2"},{"key":"104_CR26","unstructured":"Janou\u0161ek, J.: String suffix automata and subtree pushdown automata. In: Proceedings of the Prague Stringology Conference 2009, pp. 160\u2013172. Czech Technical University in Prague, Prague (2009)"},{"key":"104_CR27","unstructured":"Janou\u0161ek, J., Melichar, B.: Subtree and tree pattern pushdown automata for trees in prefix notation. Submitted for publication (2009)"},{"key":"104_CR28","unstructured":"Johnson, S.: Yacc-yet another compiler compiler. Tech. Rep. TR 32, AT & T, Bell Laboratories, New Jersey (1975)"},{"issue":"1","key":"104_CR29","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/S0019-9958(81)90438-1","volume":"49","author":"T. Kamimura","year":"1981","unstructured":"Kamimura T., Slutzki G.: Parallel and two-way automata on directed ordered acyclic graphs. Inform. Control 49(1), 10\u201351 (1981)","journal-title":"Inform. Control"},{"key":"104_CR30","doi-asserted-by":"crossref","unstructured":"Klarlund, N., Damgaard, N., Schwartzbach, M.I.: YakYak: parsing with logical side constraints. In: Developments in Language Theory, Foundations, Applications, and Perspectives, pp. 286\u2013301. World Scientific, New Jersey (2000)","DOI":"10.1142\/9789812792464_0024"},{"key":"104_CR31","unstructured":"Kron, H.: Tree templates and subtree transformational grammars. Ph.D. thesis, University of California, Santa Cruz (1975)"},{"key":"104_CR32","unstructured":"London Stringology Days 2009 Conference presentations: Available on: http:\/\/www.dcs.kcl.ac.uk\/events\/LSD&LAW09\/ (2009). King\u2019s College London, Feb 2009"},{"issue":"6","key":"104_CR33","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1145\/371880.371881","volume":"22","author":"M. Madhavan","year":"2000","unstructured":"Madhavan M., Shankar P., Siddhartha R., Ramakrishna U.: Extending Graham\u2013Glanville techniques for optimal code generation. ACM Trans. Program. Lang. Sys. 22(6), 973\u20131001 (2000)","journal-title":"ACM Trans. Program. Lang. Sys."},{"key":"104_CR34","unstructured":"Melichar, B., Holub, J., Polcar, J.: Text Searching Algorithms. Available on: http:\/\/stringology.org\/athens\/ (2005). Release Nov 2005"},{"key":"104_CR35","doi-asserted-by":"crossref","unstructured":"Melichar, B., Janou\u0161ek, J.: Repeats in Trees by Subtree and Tree Pattern Pushdown Automata. Draft (2009)","DOI":"10.1007\/978-3-642-13089-2_3"},{"issue":"1\u20132","key":"104_CR36","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0304-3975(98)00205-9","volume":"242","author":"P. Shankar","year":"2000","unstructured":"Shankar P., Gantait A., Yuvaraj A., Madhavan M.: A new algorithm for linear regular tree pattern matching. Theor. Comput. Sci. 242(1\u20132), 125\u2013142 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"104_CR37","unstructured":"Sikkel, K., Salomaa, A. (eds.): Word, language, grammar. In: Handbook of Formal Languages, vol. 1. Springer, Berlin, Heidelberg (1997)"},{"key":"104_CR38","volume-title":"Handbook of Formal Languages","year":"1997","unstructured":"Sikkel K., Salomaa A. (eds): Handbook of Formal Languages. Springer, Berlin, Heidelberg (1997b)"},{"key":"104_CR39","unstructured":"van Best, J.P.: Tree-walking automata and monadic second order logic. M.Sc. thesis, Leiden University (1998)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-009-0104-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-009-0104-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-009-0104-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T09:41:55Z","timestamp":1558690915000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-009-0104-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,1]]},"references-count":39,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["104"],"URL":"https:\/\/doi.org\/10.1007\/s00236-009-0104-9","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,1]]}}}