{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T08:22:37Z","timestamp":1725524557467},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422716"},{"type":"electronic","value":"9783540481942"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48194-x_15","type":"book-chapter","created":{"date-parts":[[2009,2,3]],"date-time":"2009-02-03T19:24:31Z","timestamp":1233689071000},"page":"157-168","source":"Crossref","is-referenced-by-count":7,"title":["Computing the Equation Automaton of a Regular Expression in O(s 2) Space and Time"],"prefix":"10.1007","author":[{"given":"Jean-Marc","family":"Champarnaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Djelloul","family":"Ziadi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,13]]},"reference":[{"key":"15_CR1","volume-title":"Data Structures and Algorithms","author":"A.V. Aho","year":"1983","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. Data Structures and Algorithms. Addison-Wesley, Reading, MA, 1983."},{"key":"15_CR2","unstructured":"J.-M. Autebert et J.-M. Rifflet. D\u00e9rivations Formelles des Expressions Rxationnelles: Un Programme de Calcul Automatique. Rapport LITP 78(14), 1978."},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","volume":"155","author":"V. Antimirov","year":"1996","unstructured":"V. Antimirov. Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci., 155:291\u2013319, 1996.","journal-title":"Theoret. Comput. Sci"},{"key":"15_CR4","unstructured":"D. Beauquier, J. Berstel, and P. Chr\u00e9tienne. \u00c9l\u00e9ments d\u2019Algorithmique. Masson, Paris, 1992."},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0304-3975(93)90287-4","volume":"120","author":"A. Br\u00fcggemann-Klein","year":"1993","unstructured":"A. Br\u00fcggemann-Klein, Regular Expressions into Finite Automata. Theoret. Comput. Sci., 120 (1993), 197\u2013213.","journal-title":"Theoret. Comput. Sci"},{"issue":"1","key":"15_CR6","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0304-3975(86)90088-5","volume":"48","author":"G. Berry","year":"1986","unstructured":"G. Berry and R. Sethi. From regular expressions to deterministic automata. Theoret. Comput. Sci., 48(1):117\u2013126, 1986.","journal-title":"Theoret. Comput. Sci"},{"issue":"4","key":"15_CR7","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"J.A. Brzozowski","year":"1964","unstructured":"J.A. Brzozowski. Derivatives of regular expressions. J. Assoc. Comput. Mach., 11(4):481\u2013494, 1964.","journal-title":"J. Assoc. Comput. Mach"},{"key":"15_CR8","series-title":"Lect Notes Comput Sci","first-page":"88","volume-title":"From Regular Expressions to DFAs using Compressed NFAs","author":"C.-H. Chang","year":"1992","unstructured":"C.-H. Chang and R. Paige. From Regular Expressions to DFAs using Compressed NFAs, in Apostolico. Crochemore. Galil. and Manber. editors. Lecture Notes in Computer Science, 644 (1992), 88\u2013108."},{"key":"15_CR9","series-title":"Lect Notes Comput Sci","volume-title":"CIAA\u2019","author":"J.-M. Champarnaud","year":"2000","unstructured":"J.-M. Champarnaud and D. Ziadi. New Finite Automaton Constructions Based on Canonical Derivatives, in CIAA\u20192000, Lecture Notes in Computer Science, S. Yu ed., Springer-Verlag, to appear."},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-662-07675-0_9","volume-title":"Handbook of Formal Languages","author":"M. Crochemore","year":"1997","unstructured":"M. Crochemore and C. Hancart. Automata for matching patterns. Handbook of Formal Languages, G. Rozenberg and A. Salomaa eds., (A.), chap. 9, 399\u2013462, Springer-Verlag, Berlin, 1997."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1070\/RM1961v016n05ABEH004112","volume":"16","author":"V.M. Glushkov","year":"1961","unstructured":"V.M. Glushkov. The abstract theory of automata. Russian Mathematical Surveys, 16:1\u201353, 1961.","journal-title":"Russian Mathematical Surveys"},{"key":"15_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BFb0055777","volume-title":"MFCS\u201998","author":"C. Hagenah","year":"1998","unstructured":"C. Hagenah and A. Muscholl, Computing \u03b5-free NFA from Regular Expressions in O(nlog2(n)) Time, in: L. Prim et al. (eds.), MFCS\u201998, Lecture Notes in Computer Science, 1450 (1998), 277\u2013285, Springer."},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1051\/ita:2000116","volume":"34\/4","author":"C. Hagenah","year":"2000","unstructured":"C. Hagenah and A. Muscholl, Computing \u03b5-free NFA from Regular Expressions in O(nlog2(n)) Time, RAIRO-TIA, 34\/4 (2000), 257\u2013278.","journal-title":"RAIRO-TIA"},{"key":"15_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BFb0023448","volume-title":"STACS\u201997","author":"J. Hromkovi\u010d","year":"1997","unstructured":"J. Hromkovi\u010d, S. Seibert and T. Wilke, Translating regular expressions into small \u03b5-free nondeterministic finite automata, in: R. Reischuk (ed.), STACS\u201997, Lecture Notes in Computer Science, 1200 (1997), 55\u201366, Springer."},{"key":"15_CR15","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA, 1979."},{"key":"15_CR16","first-page":"3","volume":"34","author":"S. Kleene","year":"1956","unstructured":"S. Kleene. Representation of events in nerve nets and finite automata. Automata Studies, Ann. Math. Studies 34:3\u201341, 1956. Princeton U. Press.","journal-title":"Automata Studies"},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1109\/TEC.1960.5221603","volume":"9","author":"R.F. McNaughton","year":"1960","unstructured":"R.F. McNaughton and H. Yamada. Regular expressions and state graphs for automata. IEEE Transactions on Electronic Computers, 9:39\u201357, March 1960.","journal-title":"IEEE Transactions on Electronic Computers"},{"key":"15_CR18","first-page":"110","volume":"5","author":"B.G. Mirkin","year":"1966","unstructured":"B.G. Mirkin. An algorithm for constructing a base in a language of regular expressions. Engineering Cybernetics, 5:110\u2013116, 1966.","journal-title":"Engineering Cybernetics"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"R. Paige and R.E. Tarjan. Three partition refinement algorithms. SIAM J. Comput., 16(6), 1987.","DOI":"10.1137\/0216062"},{"key":"15_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/3-540-63174-7_9","volume-title":"Proc.WIA\u201996","author":"J.-L. Ponty","year":"1997","unstructured":"J.-L. Ponty, D. Ziadi and J.-M. Champarnaud, A new Quadratic Algorithm to convert a Regular Expression into an Automaton, In: D. Raymond and D. Wood, eds., Proc.WIA\u201996, Lecture Notes in Computer Science, Vol. 1260 (1997) 109\u2013119."},{"key":"15_CR21","unstructured":"B. Watson, Taxonomies and Toolkits of Regular Languages Algorithms, PhD thesis, Eindhoven University of Technology, The Nederlands, 1995."},{"key":"15_CR22","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of Formal Languages","author":"S. Yu","year":"1997","unstructured":"S. Yu. Regular languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume I, Word, Language, Grammar, pages 41\u2013110. Springer-Verlag, Berlin, 1997."},{"key":"15_CR23","first-page":"177","volume":"4","author":"D. Ziadi","year":"1995","unstructured":"D. Ziadi, J.-L. Ponty, and J.-M. Champarnaud. Passage d\u2019une expression rationnelle \u00e0 un automate fini non-d\u00e9terministe. Journ\u00e9es Montoises (1995), Bull. Belg. Math. Soc., 4:177\u2013203, 1997.","journal-title":"Journ\u00e9es Montoises"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48194-X_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,23]],"date-time":"2019-02-23T15:50:01Z","timestamp":1550937001000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48194-X_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422716","9783540481942"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-48194-x_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2001]]}}}