{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:14:08Z","timestamp":1760235248878,"version":"build-2065373602"},"reference-count":21,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T00:00:00Z","timestamp":1628640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper describes a fast algorithm for constructing directly the equation automaton from the well-known Thompson automaton associated with a regular expression. Allauzen and Mohri have presented a unified construction of small automata and gave a construction of the equation automaton with time and space complexity in O(mlogm+m2), where m denotes the number of Thompson automaton transitions. It is based on two classical automata operations, namely epsilon-removal and Hopcroft\u2019s algorithm for deterministic Finite Automata (DFA) minimization. Using the notion of c-continuation, Ziadi et al. presented a fast computation of the equation automaton in O(m2) time complexity. In this paper, we design an output-sensitive algorithm combining advantages of the previous algorithms and show that its computational complexity can be reduced to O(m\u00d7|Q\u2261e|), where |Q\u2261e| denotes the number of states of the equation automaton, by an epsilon-removal and Bubenzer minimization algorithm of an Acyclic Deterministic Finite Automata (ADFA).<\/jats:p>","DOI":"10.3390\/a14080238","type":"journal-article","created":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T08:35:52Z","timestamp":1628670952000},"page":"238","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Construction of the Equation Automaton"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7636-5001","authenticated-orcid":false,"given":"Faissal","family":"Ouardi","sequence":"first","affiliation":[{"name":"Department of Computer Science, Faculty of Sciences, Mohammed V University in Rabat, Rabat 10000, Morocco"}]},{"given":"Zineb","family":"Lotfi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Sciences, Mohammed V University in Rabat, Rabat 10000, Morocco"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8034-5855","authenticated-orcid":false,"given":"Bilal","family":"Elghadyry","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Sciences, Mohammed V University in Rabat, Rabat 10000, Morocco"},{"name":"EA 4491-LISIC-Lab., Laboratoire d\u2019Informatique Signal et Image de la C\u00f4te d\u2019Opale Universit\u00e9 Littoral C\u00f4te d\u2019Opale, 62100 Calais, France"}]}],"member":"1968","published-online":{"date-parts":[[2021,8,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"694","DOI":"10.2307\/2272532","article-title":"Novyj algoritm postro\u00e9ni\u00e1 bazisa v \u00e1zyk\u00e9 r\u00e9gularnyh vyra\u017e\u00e9nij. Izv\u00e9sti\u00e1 Akad\u00e9mii Nauk SSSR. Engineering cybernetics, no. 5 (1966). English translation of the preceding: Brzozowski, J. An algorithm for constructing a base in a language of regular expressions. pp. 110\u2013116","volume":"36","author":"Mirkin","year":"1971","journal-title":"J. Symb. Log."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","article-title":"Partial derivatives of regular expressions and finite automaton constructions","volume":"155","author":"Antimirov","year":"1996","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1070\/RM1961v016n05ABEH004112","article-title":"The abstract theory of automata","volume":"16","author":"Glushkov","year":"1961","journal-title":"Russ. Math. Surv."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1109\/TEC.1960.5221603","article-title":"Regular expressions and state graphs for automata","volume":"9","author":"McNaughton","year":"1960","journal-title":"IEEE Trans. Electron. Comput."},{"key":"ref_5","unstructured":"Ziadi, D., Ponty, J.-L., and Champarnaud, J.-M. (1996, January 29\u201331). A New Quadratic Algorithm to Convert a Regular Expression into an Automaton. Proceedings of the Workshop on Implementing Automata, London, ON, Canada."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0304-3975(01)00267-5","article-title":"Canonical derivatives, partial derivatives and finite automaton constructions","volume":"289","author":"Champarnaud","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/j.jda.2007.10.003","article-title":"Fast equation automaton computation","volume":"6","author":"Khorsi","year":"2008","journal-title":"J. Discret. Algorithms"},{"key":"ref_8","unstructured":"Allauzen, C., and Mohri, M. (September, January 28). A Unified Construction of the Glushkov, Follow, and Antimirov Automata. Proceedings of the International Conference of Mathematical Foundations of Computer Science, Star\u00e1 Lesn\u00e1, Slovakia."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/S0890-5401(03)00090-7","article-title":"Follow automata","volume":"186","author":"Ilie","year":"2003","journal-title":"Inf. Comput."},{"key":"ref_10","first-page":"17","article-title":"From the ZPC Structure of a Regular Expression to its Follow Automaton","volume":"16","author":"Champarnaud","year":"2006","journal-title":"IJAC"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Kleene, S. (1956). Representation of Events in Nerve Nets and Finite Automata, Princeton University Press. Automata Studies, Ann. Math. Studies 34.","DOI":"10.1515\/9781400882618-002"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1145\/363347.363387","article-title":"Regular Expression Search Algorithm","volume":"11","author":"Thompson","year":"1968","journal-title":"Commun. ACM"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Hopcroft, J. (1971). An n log n Algorithm for Minimizing States in a Finite Automaton, Stanford University, CS Dept.. Technical Report.","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"ref_14","unstructured":"Hopcroft, J.E., and Ullman, J.D. (1979). Introduction to Automata Theory, Languages and Computation, Addison-Wesley."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Sakarovitch, J., and Thomas, R. (2009). Elements of Automata Theory, Cambridge University Press.","DOI":"10.1017\/CBO9781139195218"},{"key":"ref_16","first-page":"117","article-title":"Regular expressions into finite automata","volume":"120","year":"1993","journal-title":"Theor. Comp. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1016\/j.dam.2013.08.003","article-title":"Cycle-aware minimization of acyclic deterministic finite-state automata","volume":"163","author":"Bubenzer","year":"2014","journal-title":"J. Discret. Appl. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(92)90142-3","article-title":"Minimization of acyclic deterministic automata in linear time","volume":"92","author":"Revuz","year":"1992","journal-title":"Theor. Comput. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0166-218X(03)00299-3","article-title":"A characterization of Thompson digraphs","volume":"134","author":"Giammarresi","year":"2004","journal-title":"Discret. Appl. Math."},{"key":"ref_20","unstructured":"Myhill, J. (1957). Finite automata and the representation of events. WADD TR-57-624, Wright Patterson AFB."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","article-title":"Linear automata transformation","volume":"9","author":"Nerode","year":"1958","journal-title":"Proc. AMS"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/238\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:44:14Z","timestamp":1760165054000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,11]]},"references-count":21,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["a14080238"],"URL":"https:\/\/doi.org\/10.3390\/a14080238","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,8,11]]}}}