{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T19:13:48Z","timestamp":1620760428388},"reference-count":23,"publisher":"MIT Press - Journals","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2000,3]]},"abstract":" The paper discusses the problem of determinizing finite-state automata containing large numbers of \u03b5-moves. Experiments with finite-state approximations of natural language grammars often give rise to very large automata with a very large number of \u03b5-moves. The paper identifies and compares a number of subset construction algorithms that treat \u03b5-moves. Experiments have been performed which indicate that the algorithms differ considerably in practice, both with respect to the size of the resulting deterministic automaton, and with respect to practical efficiency. Furthermore, the experiments suggest that the average number of \u03b5-moves per state can be used to predict which algorithm is likely to be the fastest for a given input automaton. <\/jats:p>","DOI":"10.1162\/089120100561638","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:56:30Z","timestamp":1027770990000},"page":"61-76","source":"Crossref","is-referenced-by-count":14,"title":["Treatment of Epsilon Moves in Subset Construction"],"prefix":"10.1162","volume":"26","author":[{"given":"Gertjan van","family":"Noord","sequence":"first","affiliation":[{"name":"Rijksuniversiteit Groningen, Alfa-informatica & BCN."}]}],"member":"281","reference":[{"key":"p_1_72","unstructured":"Aho, Alfred V., Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers. Principles, Techniques and Tools. Addison Wesley."},{"key":"p_2_73","unstructured":"Black, Alan W. 1989. Finite state machines from feature grammars. In International Workshop on Parsing Technologies, pages 277-285, Pittsburgh, PA."},{"key":"p_3_74","unstructured":"Chomsky, Noam. 1963. Formal properties of grammars. In R. Duncan Luce, Robert R. Bush, and Eugene Galanter, editors, Handbook of Mathematical Psychology; Volume II. John Wiley, pages 323-418."},{"key":"p_4_75","unstructured":"Chomsky, Noam. 1964. On the notion `rule of grammar.' In Jerry E. Fodor and Jerrold J. Katz, editors, The Structure of Language; Readings in the Philosophy of Language. Prentice Hall, pages 119-136."},{"key":"p_5_76","unstructured":"Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA."},{"key":"p_6_77","doi-asserted-by":"crossref","unstructured":"Gerdemann, Dale and Gertjan van Noord. 1999. Transducers from rewrite rules with backreferences. In Ninth Conference of the European Chapter of the Association for Computational Linguistics, Bergen, Norway.","DOI":"10.3115\/977035.977053"},{"key":"p_7_78","doi-asserted-by":"crossref","unstructured":"Grimley-Evans, Edmund. 1997. Approximating context-free grammars with a finite-state calculus. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, pages 452-459, Madrid, Spain.","DOI":"10.3115\/976909.979675"},{"key":"p_8_79","unstructured":"Hopcroft, John E. and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA."},{"key":"p_9_80","doi-asserted-by":"crossref","unstructured":"Johnson, J. Howard and Derick Wood. 1997. Instruction computation in subset construction. In Darrell Raymond, Derick Wood, and Sheng Yu, editors, Automata Implementation. Springer Verlag, pages 64-71. Lecture Notes in Computer Science 1260.","DOI":"10.1007\/3-540-63174-7_6"},{"key":"p_10_81","doi-asserted-by":"crossref","unstructured":"Johnson, Mark. 1998. Finite-state approximation of constraint-based grammars using left-corner grammar transforms. In COLING-ACL '98: 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics. Proceedings of the Conference, pages 619-623, Montreal, Quebec, Canada.","DOI":"10.3115\/980845.980948"},{"key":"p_11_82","unstructured":"Leslie, Ted. 1995. Efficient approaches to subset construction. Master's thesis, Computer Science, University of Waterloo."},{"key":"p_12_83","unstructured":"Miller, George and Noam Chomsky. 1963. Finitary models of language users. In R. Luce, R. Bush, and E. Galanter, editors, Handbook of Mathematical Psychology. Volume 2. John Wiley, pages 419-491."},{"key":"p_13_84","doi-asserted-by":"crossref","unstructured":"Mohri, Mehryar, Fernando C. N. Pereira, and Michael Riley. 1998. A rational design for a weighted finite-state transducer library. In Derick Wood and Sheng Yu, editors, Automata Implementation. Lecture Notes in Computer Science, Number 1436. Springer Verlag, pages 144-158.","DOI":"10.1007\/BFb0031388"},{"key":"p_14_85","unstructured":"Nederhof, Mark-Jan. 1997. Regular approximations of CFLs: A grammatical view. In Proceedings of the International Workshop on Parsing Technologies, pages 159-170, Massachusetts Institute of Technology."},{"key":"p_15_86","doi-asserted-by":"crossref","unstructured":"Nederhof, Mark-Jan. 1998. Context-free parsing through regular approximation. In Proceedings of the International Workshop on Finite-state Methods in Natural Language Processing, pages 13-24, Ankara, Turkey.","DOI":"10.3115\/1611533.1611535"},{"key":"p_16_87","unstructured":"O'Keefe, Richard A. 1990. The Craft of Prolog. MIT Press, Cambridge, MA."},{"key":"p_17_88","doi-asserted-by":"crossref","unstructured":"Pereira, Fernando C. N. and Rebecca N. Wright. 1991. Finite-state approximation of phrase structure grammars. In Proceedings of the 29th Annual Meeting, pages 246-255, Berkeley. Association for Computational Linguistics.","DOI":"10.3115\/981344.981376"},{"key":"p_18_89","unstructured":"Pereira, Fernando C. N. and Rebecca N. Wright. 1997. Finite-state approximation of phrase-structure grammars. In Emmanuel Roche and Yves Schabes, editors, Finite-State Language Processing. MIT Press, Cambridge, MA, pages 149-173."},{"key":"p_19_90","unstructured":"Rood, C. M. 1996. Efficient finite-state approximation of context free grammars. In A. Kornai, editor, Extended Finite State Models of Language, Proceedings of the ECAI'96 workshop, pages 58-64, Budapest University of Economic Sciences, Hungary."},{"key":"p_20_91","doi-asserted-by":"crossref","unstructured":"van Noord, Gertjan. 1997. FSA Utilities: A toolbox to manipulate finite-state automata. In Darrell Raymond, Derick Wood, and Sheng Yu, editors, Automata Implementation. Lecture Notes in Computer Science, Number 1260. Springer Verlag, pages 87-108.","DOI":"10.1007\/3-540-63174-7_8"},{"key":"p_21_92","unstructured":"van Noord, Gertjan. 1998. The treatment of epsilon moves in subset construction. In Proceedings of the International Workshop on Finite-state Methods in Natural Language Processing, pages 57-68, Ankara, Turkey. cmp-lg\/9804003."},{"key":"p_22_93","unstructured":"van Noord, Gertjan. 1999. FSA6 reference manual. The FSA Utilities toolbox is available free of charge under Gnu General Public License at http:\/\/www.let.rug.nl\/~vannoord\/Fsa\/."},{"key":"p_23_94","unstructured":"van Noord, Gertjan and Dale Gerdemann. 1999. An extendible regular expression compiler for finite-state approaches in natural language processing. In O. Boldt, H. Juergensen, and L. Robbins, editors, Workshop on Implementing Automata; WIA99 Pre-Proceedings, pages XIV-1-XIV-15, Potsdam, Germany."}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/089120100561638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:41:38Z","timestamp":1615585298000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,3]]}},"alternative-id":["10.1162\/089120100561638"],"URL":"http:\/\/dx.doi.org\/10.1162\/089120100561638","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":["Artificial Intelligence","Computer Science Applications","Linguistics and Language","Language and Linguistics"],"published":{"date-parts":[[2000,3]]}}}