{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T23:55:36Z","timestamp":1768694136727,"version":"3.49.0"},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p> Antimirov and Mosses proposed a rewrite system for deciding the equivalence of two (extended) regular expressions. They argued that this method could lead to a better average-case algorithm than those based on the comparison of the equivalent minimal deterministic finite automata. In this paper we present a functional approach to that method, prove its correctness, and give some experimental comparative results. Besides an improved functional version of Antimirov and Mosses's algorithm, we present an alternative one using partial derivatives. Our preliminary results lead to the conclusion that, indeed, these methods are feasible and, most of the time, faster than the classical methods. <\/jats:p>","DOI":"10.1142\/s0129054109006802","type":"journal-article","created":{"date-parts":[[2009,7,29]],"date-time":"2009-07-29T11:44:22Z","timestamp":1248867862000},"page":"669-684","source":"Crossref","is-referenced-by-count":15,"title":["ANTIMIROV AND MOSSES'S REWRITE SYSTEM REVISITED"],"prefix":"10.1142","volume":"20","author":[{"given":"MARCO","family":"ALMEIDA","sequence":"first","affiliation":[{"name":"LIACC, Faculdade de Ci\u00eancias, Universidade do Porto, Departamento de Ci\u00eancia de Computadores, Rua do Campo Alegre, 1021\/1055, 4169-007 Porto, Portugal"}]},{"given":"NELMA","family":"MOREIRA","sequence":"additional","affiliation":[{"name":"LIACC, Faculdade de Ci\u00eancias, Universidade do Porto, Departamento de Ci\u00eancia de Computadores, Rua do Campo Alegre, 1021\/1055, 4169-007 Porto, Portugal"}]},{"given":"ROG\u00c9RIO","family":"REIS","sequence":"additional","affiliation":[{"name":"LIACC, Faculdade de Ci\u00eancias, Universidade do Porto, Departamento de Ci\u00eancia de Computadores, Rua do Campo Alegre, 1021\/1055, 4169-007 Porto, Portugal"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","unstructured":"V. M.\u00a0Antimirov and P. D.\u00a0Mosses, Developments in Language Theory, eds. G.\u00a0Rozenberg and A.\u00a0Salomaa (World Scientific, 1994)\u00a0pp. 195\u2013209."},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.029"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"rf8","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2003"},{"key":"rf9","first-page":"407","volume":"10","author":"Ellul K.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"rf12","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J.","year":"2000"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00090-7"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1037"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1844-9"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69959-7"},{"key":"rf17","series-title":"LNCS","first-page":"2","volume":"3314","author":"Lee J.","year":"2005"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90033-7"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1145\/321312.321326"},{"key":"rf21","first-page":"410","volume":"11","author":"Thompson K.","journal-title":"Communications of the ACM"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054109006802","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T04:39:01Z","timestamp":1565152741000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054109006802"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":17,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1142\/S0129054109006802"],"URL":"https:\/\/doi.org\/10.1142\/s0129054109006802","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}