{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,20]],"date-time":"2022-06-20T23:26:19Z","timestamp":1655767579488},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,9]]},"abstract":"<jats:p>Champarnaud et al., and Khorsi et al. show how to compute the equation automaton of a word regular expression [Formula: see text] via the C-continuations. Kuske and Meinecke extend the computation of the equation automaton to a regular tree expression [Formula: see text] over a ranked alphabet [Formula: see text] and produce a [Formula: see text] time and space complexity algorithm, where [Formula: see text] is the maximal rank of a symbol occurring in [Formula: see text] and [Formula: see text] is the size of the syntax tree of [Formula: see text]. In this paper, we give a full description of an algorithm based on the acyclic minimization of Revuz in order to compute the pseudo-continuations from the C-continuations. Our algorithm, which is performed in [Formula: see text] time and space complexity, where [Formula: see text] is the number of states of the produced automaton, is more efficient than the one obtained by Kuske and Meinecke since [Formula: see text]. Moreover, our algorithm is an output-sensitive algorithm, i.e. the complexity of which is based on the size of the produced automaton.<\/jats:p>","DOI":"10.1142\/s0129054118500156","type":"journal-article","created":{"date-parts":[[2018,10,5]],"date-time":"2018-10-05T08:02:35Z","timestamp":1538726555000},"page":"951-978","source":"Crossref","is-referenced-by-count":1,"title":["An Efficient Algorithm for the Construction of the Equation Tree Automaton"],"prefix":"10.1142","volume":"29","author":[{"given":"Ludovic","family":"Mignot","sequence":"first","affiliation":[{"name":"D\u00e9partement d\u2019informatique, Universit\u00e9 de Rouen Normandie, 76801 Saint-\u00c9tienne du Rouvray Cedex, France"}]},{"given":"Nadia","family":"Ouali-Sebti","sequence":"additional","affiliation":[{"name":"D\u00e9partement d\u2019informatique, Universit\u00e9 de Rouen Normandie, 76801 Saint-\u00c9tienne du Rouvray Cedex, France"}]},{"given":"Djelloul","family":"Ziadi","sequence":"additional","affiliation":[{"name":"D\u00e9partement d\u2019informatique, Universit\u00e9 de Rouen Normandie, 76801 Saint-\u00c9tienne du Rouvray Cedex, France"}]}],"member":"219","published-online":{"date-parts":[[2018,10,5]]},"reference":[{"key":"S0129054118500156BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"S0129054118500156BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90287-4"},{"key":"S0129054118500156BIB003","first-page":"90","volume-title":"CIAA, Lecture Notes in Computer Science","volume":"3317","author":"Champarnaud J.","year":"2004"},{"key":"S0129054118500156BIB004","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196701000772"},{"key":"S0129054118500156BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00267-5"},{"key":"S0129054118500156BIB007","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"S0129054118500156BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00090-7"},{"key":"S0129054118500156BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2007.10.003"},{"key":"S0129054118500156BIB010","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2011107"},{"key":"S0129054118500156BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37064-9_35"},{"key":"S0129054118500156BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08019-2_31"},{"key":"S0129054118500156BIB013","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1958-0135681-9"},{"key":"S0129054118500156BIB014","doi-asserted-by":"publisher","DOI":"10.1137\/0216062"},{"key":"S0129054118500156BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90142-3"},{"key":"S0129054118500156BIB017","doi-asserted-by":"crossref","first-page":"177","DOI":"10.36045\/bbms\/1105730628","volume":"4","author":"Ziadi D.","year":"1997","journal-title":"Bulletin of the Belgian Mathematical Society - Simon Stevin"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118500156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T12:27:22Z","timestamp":1572006442000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118500156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9]]},"references-count":15,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2018,10,5]]},"published-print":{"date-parts":[[2018,9]]}},"alternative-id":["10.1142\/S0129054118500156"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118500156","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9]]}}}