{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T10:40:01Z","timestamp":1734950401528,"version":"3.32.0"},"reference-count":0,"publisher":"World Scientific Pub Co Pte Ltd","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"abstract":"<jats:p> The partial derivative automaton ([Formula: see text]) is an elegant simulation of a regular expression. Although it is, in general, smaller than the position automaton ([Formula: see text]), the algorithms that build [Formula: see text] in quadratic worst-case time first compute [Formula: see text]. Asymptotically, and on average for the uniform distribution, the size of [Formula: see text] is half the size of [Formula: see text], being both linear on the size of the expression. We address the construction of [Formula: see text] efficiently, on average, avoiding the computation of [Formula: see text]. The expression and the set of its partial derivatives are represented by a directed acyclic graph with shared common subexpressions. We develop an algorithm for building [Formula: see text]s from expressions in strong star normal form of size [Formula: see text] that runs, on average, in time that asymptotically behaves as [Formula: see text], and space as [Formula: see text]. Empirical results corroborate its good practical performance. <\/jats:p>","DOI":"10.1142\/s0129054124420061","type":"journal-article","created":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T09:28:17Z","timestamp":1734946097000},"page":"1-23","source":"Crossref","is-referenced-by-count":0,"title":["Compressed Structures for Partial Derivative Automata Constructions"],"prefix":"10.1142","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6628-067X","authenticated-orcid":false,"given":"Stavros","family":"Konstantinidis","sequence":"first","affiliation":[{"name":"Saint Mary\u2019s University, Halifax, Nova Scotia, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7595-7275","authenticated-orcid":false,"given":"Ant\u00f3nio","family":"Machiavelo","sequence":"additional","affiliation":[{"name":"CMUP & DM, DCC, Faculdade de Ci\u00eancias da Universidade do Porto, Rua do Campo Alegre, 4169-007 Porto, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0861-0105","authenticated-orcid":false,"given":"Nelma","family":"Moreira","sequence":"additional","affiliation":[{"name":"CMUP & DM, DCC, Faculdade de Ci\u00eancias da Universidade do Porto, Rua do Campo Alegre, 4169-007 Porto, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9668-0917","authenticated-orcid":false,"given":"Rog\u00e9rio","family":"Reis","sequence":"additional","affiliation":[{"name":"CMUP & DM, DCC, Faculdade de Ci\u00eancias da Universidade do Porto, Rua do Campo Alegre, 4169-007 Porto, Portugal"}]}],"member":"219","published-online":{"date-parts":[[2024,12,23]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054124420061","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T09:28:20Z","timestamp":1734946100000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054124420061"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,23]]},"references-count":0,"alternative-id":["10.1142\/S0129054124420061"],"URL":"https:\/\/doi.org\/10.1142\/s0129054124420061","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2024,12,23]]}}}