{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T08:00:01Z","timestamp":1770278401200,"version":"3.49.0"},"reference-count":12,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T00:00:00Z","timestamp":1626912000000},"content-version":"vor","delay-in-days":202,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2021,5,26]]},"published-print":{"date-parts":[[2021]]},"abstract":"<jats:p>In this paper, we extend the notion of (word) derivatives and partial derivatives due to (respectively) Brzozowski and Antimirov to tree derivatives using already known inductive formulae of quotients. We define a new family of extended regular tree expressions (using negation or intersection operators), and we show how to compute a Brzozowski-like inductive tree automaton; the fixed point of this construction, when it exists, is the derivative tree automaton. Such a deterministic tree automaton can be used to solve the membership test efficiently: the whole structure is not necessarily computed, and the derivative computations can be performed in parallel. We also show how to solve the membership test using our (Bottom-Up) partial derivatives, without computing an automaton.<\/jats:p>","DOI":"10.1051\/ita\/2021008","type":"journal-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T07:56:03Z","timestamp":1627026963000},"page":"4","source":"Crossref","is-referenced-by-count":1,"title":["Bottom-Up derivatives of tree expressions"],"prefix":"10.1051","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8463-0840","authenticated-orcid":false,"given":"Samira","family":"Attou","sequence":"first","affiliation":[]},{"given":"Ludovic","family":"Mignot","sequence":"additional","affiliation":[]},{"given":"Djelloul","family":"Ziadi","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2021,7,22]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","volume":"155","author":"Antimirov","year":"1996","journal-title":"Theor. Comput. Sci"},{"key":"R2","unstructured":"Attou S., \nMignot L. and \nZiadi D., \nExtended tree expressions and their derivatives, in NCMA, Valencia, Spain, \nJuly 2\u20133, 2019 \n(2019) 47\u201362."},{"key":"R3","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"Brzozowski","year":"1964","journal-title":"J. ACM"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Caron P., \nChamparnaud J. and \nMignot L., Partial derivatives of an extended regular expression, in LATA, vol. 6638 of \nLecture Notes in Computer Science. \nSpringer \n(2011) 179\u2013191.","DOI":"10.1007\/978-3-642-21254-3_13"},{"key":"R5","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1051\/ita\/2014010","volume":"48","author":"Caron","year":"2014","journal-title":"RAIRO - Theor. Inf. Appl."},{"key":"R6","first-page":"243","volume":"22","author":"Champarnaud","year":"2017","journal-title":"J. Autom. Lang. Combinat"},{"key":"R7","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1017\/S0956796897002864","volume":"7","author":"Huet","year":"1997","journal-title":"J. Funct. Program"},{"key":"R8","first-page":"3","volume":"34","author":"Kleene","year":"1956","journal-title":"Automata Studies, Ann. Math. Stud"},{"key":"R9","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1051\/ita\/2011107","volume":"45","author":"Kuske","year":"2011","journal-title":"RAIRO \u2013 Theor. Inf. Appl."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Laugerotte \u00c9., \nLuque J.-G., \nMignot L. and \nNicart F., \nMultilinear representations of free pros. \nLinear Multilinear Algeb. \n(2019) 1\u201345.","DOI":"10.1080\/03081087.2019.1566430"},{"key":"R11","unstructured":"Mignot L., \nApplication: Bottom up derivatives. \nhttp:\/\/ludovicmignot.free.fr\/programmes\/BottomUpPartialDerivatives\/index.html. Accessed: \n2019-12-08."},{"key":"R12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"Thatcher","year":"1968","journal-title":"Math. Syst. Theory"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2021008\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T07:56:13Z","timestamp":1627026973000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2021008"}},"subtitle":[],"editor":[{"given":"Markus","family":"Holzer","sequence":"first","affiliation":[]},{"given":"Jos\u00e9 M.","family":"Sempere","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":12,"alternative-id":["ita190044"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2021008","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]}}}