{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:18:14Z","timestamp":1755998294306},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,9,24]],"date-time":"2014-09-24T00:00:00Z","timestamp":1411516800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,7]]},"DOI":"10.1007\/s00224-014-9576-2","type":"journal-article","created":{"date-parts":[[2014,9,23]],"date-time":"2014-09-23T23:56:23Z","timestamp":1411516583000},"page":"97-139","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Deciding Determinism of Regular Languages"],"prefix":"10.1007","volume":"57","author":[{"given":"Ping","family":"Lu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Bremer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haiming","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,24]]},"reference":[{"key":"9576_CR1","doi-asserted-by":"crossref","unstructured":"Ahonen, H.: Disambiguation of SGML content models. In: PODP of LNCS, vol. 1293 pp. 27\u201337. Springer (1996)","DOI":"10.1007\/3-540-63620-X_53"},{"key":"9576_CR2","doi-asserted-by":"crossref","unstructured":"Bex, G. J., Gelade, W., Martens, W., Neven, F.: Simplifying XML schema: effortless handling of nondeterministic regular expressions. In: SIGMOD Conference. pp. 731\u2013744. ACM (2009)","DOI":"10.1145\/1559845.1559922"},{"issue":"2","key":"9576_CR3","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0304-3975(93)90287-4","volume":"120","author":"A Br\u00fcggemann-Klein","year":"1993","unstructured":"Br\u00fcggemann-Klein, A.: Regular expressions into finite automata. Theor. Comput. Sci. 120(2), 197\u2013213 (1993)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9576_CR4","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. 140 (2), 182\u2013206 (1998)","journal-title":"Inf. Comput."},{"key":"9576_CR5","doi-asserted-by":"crossref","unstructured":"Caron, P., Han, Y., Mignot, L.: Generalized one-unambiguity. In: Developments in Language Theory of LNCS, vol. 6795 pp. 129\u2013140. Springer (2011)","DOI":"10.1007\/978-3-642-22321-1_12"},{"key":"9576_CR6","doi-asserted-by":"crossref","unstructured":"Chen, H., Lu, P.: Assisting the design of XML schema: diagnosing nondeterministic content models. In: APWeb of LNCS, vol. 6612 pp. 301\u2013312 Springer (2011).","DOI":"10.1007\/978-3-642-20291-9_31"},{"key":"9576_CR7","doi-asserted-by":"crossref","unstructured":"Chen, H., Lu, P.: Checking determinism of regular expressions with counting. In: Developments in Language Theory of LNCS, vol. 7410 pp. 332\u2013343 Springer (2012).","DOI":"10.1007\/978-3-642-31653-1_30"},{"key":"9576_CR8","doi-asserted-by":"crossref","unstructured":"Czerwi\u0144ski, W., David, C., Losemann, K., Martens, W.: Deciding definability by deterministic regular expressions. In: FoSSaCS, of LNCS, vol. 7794 pp. 289\u2013304. Springer (2013)","DOI":"10.1007\/978-3-642-37075-5_19"},{"key":"9576_CR9","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman (1979)."},{"issue":"1","key":"9576_CR10","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1137\/100814196","volume":"41","author":"W Gelade","year":"2012","unstructured":"Gelade, W., Gyssens, M., Martens, W.: regular expressions with counting: weak versus strong determinism. SIAM J. Comput. 41 (1), 160\u2013190 (2012).","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9576_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1070\/RM1961v016n05ABEH004112","volume":"16","author":"VM Glushkov","year":"1961","unstructured":"Glushkov, V. M.: The abstract theory of automata. Russian Math. Surveys 16(5), 1\u201353 (1961)","journal-title":"Russian Math. Surveys"},{"key":"9576_CR12","doi-asserted-by":"crossref","unstructured":"Groz, B., Maneth, S., Staworko, S.: Deterministic regular expressions in linear time. In: PODS, pp. 49\u201360. ACM (2012)","DOI":"10.1145\/2213556.2213566"},{"key":"9576_CR13","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.: An n logn algorithm for minimizing states in a finite automaton. Theory of machines and Computations (1971)","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"9576_CR14","unstructured":"Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)."},{"key":"9576_CR15","doi-asserted-by":"crossref","unstructured":"Hovland, D.: The Membership problem for regular expressions with unordered concatenation and numerical constraints. In: LATA of LNCS, vol. 7183 , pp. 313\u2013324. Springer (2012).","DOI":"10.1007\/978-3-642-28332-1_27"},{"issue":"5","key":"9576_CR16","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput. 17(5), 935\u2013938 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9576_CR17","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"ND Jones","year":"1975","unstructured":"Jones, N. D.: Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11(1), 68\u201385 (1975)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9576_CR18","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1016\/j.is.2010.10.001","volume":"36","author":"P Kilpel\u00e4inen","year":"2011","unstructured":"Kilpel\u00e4inen, P.: Checking determinism of XML Schema content models in optimal time. Information Systems. 36(3), 596\u2013617 (2011)","journal-title":"Information Systems"},{"issue":"3","key":"9576_CR19","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s00778-005-0169-1","volume":"16","author":"C Koch","year":"2007","unstructured":"Koch, C., Scherzinger, S.: Attribute grammars for scalable query processing on XML streams. VLDB J. 16(3), 317\u2013342 (2007)","journal-title":"VLDB J."},{"key":"9576_CR20","doi-asserted-by":"crossref","unstructured":"Losemann, K., Martens, W., Niewerth, M.: Descriptional complexity of deterministic regular expressions. In: MFCS of LNCS, vol. 7464, pp. 643\u2013654. Springer (2012)","DOI":"10.1007\/978-3-642-32589-2_56"},{"key":"9576_CR21","doi-asserted-by":"crossref","unstructured":"Meyer, A. R., Stockmeyer, L. J.: The equivalence problem for regular expressions with squaring requires exponential space. In: SWAT (FOCS), pp. 125\u2013129. IEEE Computer Society (1972)","DOI":"10.1109\/SWAT.1972.29"},{"key":"9576_CR22","unstructured":"Papadimitriou, C. H: Computational Complexity. Addison-Wesley (1994)"},{"key":"9576_CR23","doi-asserted-by":"crossref","unstructured":"Rozenberg, G., Salomaa, A., (Eds): Handbook of Formal Languages, vol. 1: Word, Language, Grammar. Springer-Verlag New York, New York (1997)","DOI":"10.1007\/978-3-642-59136-5"},{"key":"9576_CR24","unstructured":"Sperberg-McQueen, C. M: Notes on finite state automata with counters (2004)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9576-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9576-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9576-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,15]],"date-time":"2019-08-15T09:22:50Z","timestamp":1565860970000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9576-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,24]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["9576"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9576-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,24]]}}}