{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T22:18:49Z","timestamp":1670278729470},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,10,26]],"date-time":"2012-10-26T00:00:00Z","timestamp":1351209600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,4]]},"DOI":"10.1007\/s00224-012-9428-x","type":"journal-article","created":{"date-parts":[[2012,10,25]],"date-time":"2012-10-25T10:05:23Z","timestamp":1351159523000},"page":"542-585","source":"Crossref","is-referenced-by-count":2,"title":["Generating, Sampling and Counting Subclasses of Regular Tree Languages"],"prefix":"10.1007","volume":"52","author":[{"given":"Timos","family":"Antonopoulos","sequence":"first","affiliation":[]},{"given":"Floris","family":"Geerts","sequence":"additional","affiliation":[]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,10,26]]},"reference":[{"issue":"1\u20132","key":"9428_CR1","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/S0304-3975(00)00294-2","volume":"267","author":"J. Albert","year":"2001","unstructured":"Albert, J., Giammerresi, D., Wood, D.: Normal form algorithms for extended context free grammars. Theor. Comput. Sci. 267(1\u20132), 35\u201347 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9428_CR2","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.tcs.2007.07.029","volume":"387","author":"M. Almeida","year":"2007","unstructured":"Almeida, M., Moreira, N., Reis, R.: Enumeration and generation with a string automata representation. Theor. Comput. Sci. 387(2), 93\u2013102 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9428_CR3","first-page":"616","volume-title":"International Symposium on Management of Data (SIGMOD)","author":"D. Barbosa","year":"2002","unstructured":"Barbosa, D., Mendelzon, A.O., Keenleyside, J., Lyons, K.A.: ToXgene: a\u00a0template-based data generator for XML. In: International Symposium on Management of Data (SIGMOD), p.\u00a0616 (2002)"},{"issue":"2\u20133","key":"9428_CR4","first-page":"1","volume":"19","author":"F. Bassino","year":"2008","unstructured":"Bassino, F., David, J., Nicaud, C.: Enumeration and random generation of possibly incomplete deterministic automata. Pure Math. Appl. 19(2\u20133), 1\u201316 (2008)","journal-title":"Pure Math. Appl."},{"issue":"1\u20133","key":"9428_CR5","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.tcs.2007.04.001","volume":"381","author":"F. Bassino","year":"2007","unstructured":"Bassino, F., Nicaud, C.: Enumeration and random generation of accessible automata. Theor. Comput. Sci. 381(1\u20133), 86\u2013104 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9428_CR6","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(91)90023-U","volume":"86","author":"A. Bertoni","year":"1991","unstructured":"Bertoni, A., Goldwurm, M., Sabadini, N.: The complexity of computing the number of strings of given length in context-free languages. Theor. Comput. Sci. 86(2), 325\u2013342 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"9428_CR7","first-page":"731","volume-title":"International Symposium on Management of Data (SIGMOD)","author":"G.J. Bex","year":"2009","unstructured":"Bex, G.J., Gelade, W., Martens, W., Neven, F.: Simplifying XML schema: effortless handling of nondeterministic regular expressions. In: International Symposium on Management of Data (SIGMOD), pp. 731\u2013744 (2009)"},{"key":"9428_CR8","first-page":"825","volume-title":"International World Wide Web Conference (WWW)","author":"G.J. Bex","year":"2008","unstructured":"Bex, G.J., Gelade, W., Neven, F., Vansummeren, S.: Learning deterministic regular expressions for the inference of schemas from XML data. In: International World Wide Web Conference (WWW), pp. 825\u2013834 (2008)"},{"key":"9428_CR9","doi-asserted-by":"crossref","unstructured":"Bex, G.J., Gelade, W., Neven, F., Vansummeren, S.: Learning deterministic regular expressions for the inference of schemas from XML data. ACM Trans. Web 4(4) (2010)","DOI":"10.1145\/1841909.1841911"},{"key":"9428_CR10","doi-asserted-by":"crossref","unstructured":"Bex, G.J., Neven, F., Schwentick, T., Vansummeren, S.: Inference of concise regular expressions and DTDs. ACM Transactions on Database Systems (2010)","DOI":"10.1145\/1735886.1735890"},{"key":"9428_CR11","first-page":"998","volume-title":"International Conference on Very Large Data Bases (VLDB)","author":"G.J. Bex","year":"2007","unstructured":"Bex, G.J., Neven, F., Vansummeren, S.: Inferring XML schema definitions from XML data. In: International Conference on Very Large Data Bases (VLDB), pp. 998\u20131009 (2007)"},{"key":"9428_CR12","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/978-3-540-70583-3_3","volume-title":"International Colloquium on Automata, Languages and Programming (ICALP)","author":"H. Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, H., Martens, W.: The tractability frontier for NFA minimization. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 27\u201338 (2008)"},{"key":"9428_CR13","first-page":"87","volume-title":"Latin American Symposium on Theoretical Informatics (LATIN)","author":"A. Br\u00fcggemann-Klein","year":"1992","unstructured":"Br\u00fcggemann-Klein, A.: Regular expressions into finite automata. In: Latin American Symposium on Theoretical Informatics (LATIN), pp. 87\u201398 (1992)"},{"key":"9428_CR14","unstructured":"Br\u00fcggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets: version\u00a01, April\u00a03. Technical report HKUST-TCSC-2001-0, The Hongkong University of Science and Technology (2001)"},{"issue":"2","key":"9428_CR15","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1006\/inco.1997.2695","volume":"142","author":"A. Br\u00fcggemann-Klein","year":"1998","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Inf. Comput. 142(2), 182\u2013206 (1998)","journal-title":"Inf. Comput."},{"issue":"3","key":"9428_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1567274.1567280","volume":"34","author":"S. Cohen","year":"2009","unstructured":"Cohen, S., Kimelfeld, B., Sagiv, Y.: Incorporating constraints in probabilistic XML. ACM Trans. Database Syst. 34(3), 1\u201345 (2009)","journal-title":"ACM Trans. Database Syst."},{"key":"9428_CR17","first-page":"227","volume-title":"International Symposium on Principles of Database Systems (PODS)","author":"S. Cohen","year":"2009","unstructured":"Cohen, S., Kimelfeld, B., Sagiv, Y.: Running tree automata on probabilistic XML. In: International Symposium on Principles of Database Systems (PODS), pp. 227\u2013236 (2009)"},{"issue":"2","key":"9428_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(94)90226-7","volume":"132","author":"P. Flajolet","year":"1994","unstructured":"Flajolet, P., Zimmermann, P., Van Cutsem, B.: A\u00a0calculus for the random generation of labelled combinatorial structures. Theor. Comput. Sci. 132(2), 1\u201335 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"9428_CR19","volume-title":"International Symposium on Principles of Database Systems (PODS)","author":"W. Gelade","year":"2010","unstructured":"Gelade, W., Idziaszek, T., Martens, W., Neven, F.: Simplifying XML schema: single-type approximations of regular tree languages. In: International Symposium on Principles of Database Systems (PODS) (2010)"},{"issue":"3","key":"9428_CR20","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1016\/j.jcss.2010.04.008","volume":"77","author":"W. Gelade","year":"2011","unstructured":"Gelade, W., Neven, F.: Succinctness of pattern-based schema languages for XML. J. Comput. Syst. Sci. 77(3), 505\u2013519 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9428_CR21","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1006\/inco.1997.2621","volume":"134","author":"V. Gore","year":"1997","unstructured":"Gore, V., Jerrum, M., Kannan, S., Sweedyk, Z., Mahaney, S.R.: A\u00a0quasi-polynomial-time algorithm for sampling words from a context-free language. Inf. Comput. 134(1), 59\u201374 (1997)","journal-title":"Inf. Comput."},{"key":"9428_CR22","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/978-3-642-02979-0_15","volume-title":"International Conference on Implementation and Application of Automata (CIAA)","author":"P.-C. H\u00e9am","year":"2009","unstructured":"H\u00e9am, P.-C., Nicaud, C., Schmitz, S.: Random generation of deterministic tree (walking) automata. In: International Conference on Implementation and Application of Automata (CIAA), pp. 115\u2013124 (2009)"},{"key":"9428_CR23","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"2007","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley, Reading (2007)","edition":"3"},{"key":"9428_CR24","first-page":"551","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"S. Kannan","year":"1995","unstructured":"Kannan, S., Sweedyk, Z., Mahaney, S.R.: Counting and random generation of strings in regular languages. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 551\u2013557 (1995)"},{"issue":"3","key":"9428_CR25","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/1324185.1324188","volume":"36","author":"W. Martens","year":"2007","unstructured":"Martens, W., Neven, F., Schwentick, T.: Simple off the shelf abstractions of XML schema. SIGMOD Rec. 36(3), 15\u201322 (2007)","journal-title":"SIGMOD Rec."},{"issue":"4","key":"9428_CR26","doi-asserted-by":"crossref","first-page":"1486","DOI":"10.1137\/080743457","volume":"39","author":"W. Martens","year":"2009","unstructured":"Martens, W., Neven, F., Schwentick, T.: Complexity of decision problems for XML schemas and chain regular expressions. SIAM J. Comput. 39(4), 1486\u20131530 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9428_CR27","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1145\/1166074.1166076","volume":"31","author":"W. Martens","year":"2006","unstructured":"Martens, W., Neven, F., Schwentick, T., Bex, G.J.: Expressiveness and complexity of XML schema. ACM Trans. Database Syst. 31(3), 770\u2013813 (2006)","journal-title":"ACM Trans. Database Syst."},{"issue":"4","key":"9428_CR28","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1016\/j.jcss.2006.10.021","volume":"73","author":"W. Martens","year":"2007","unstructured":"Martens, W., Niehren, J.: On the minimization of XML Schemas and tree automata for unranked trees. J. Comput. Syst. Sci. 73(4), 550\u2013583 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"9428_CR29","first-page":"188","volume-title":"FOCS","author":"A.R. Meyer","year":"1971","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: FOCS, pp. 188\u2013191. IEEE, New York (1971)"},{"issue":"4","key":"9428_CR30","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1145\/1111627.1111631","volume":"5","author":"M. Murata","year":"2005","unstructured":"Murata, M., Lee, D., Mani, M., Kawaguchi, K.: Taxonomy of XML schema languages using formal language theory. ACM Trans. Internet Technol. 5(4), 660\u2013704 (2005)","journal-title":"ACM Trans. Internet Technol."},{"key":"9428_CR31","volume-title":"Combinatorial Algorithms","author":"A. Nijenhuis","year":"1979","unstructured":"Nijenhuis, A., Wilf, H.: Combinatorial Algorithms. Academic Press, San Diego (1979)"},{"issue":"3","key":"9428_CR32","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1137\/0219027","volume":"19","author":"H. Seidl","year":"1990","unstructured":"Seidl, H.: Deciding equivalence of finite tree automata. SIAM J. Comput. 19(3), 424\u2013437 (1990)","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9428-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-012-9428-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9428-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,5]],"date-time":"2019-07-05T00:11:23Z","timestamp":1562285483000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9428-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,26]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["9428"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9428-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,26]]}}}