{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:23:18Z","timestamp":1770963798350,"version":"3.50.1"},"reference-count":16,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>Synchronised shuffle operators allow to specify symbols on which the operands must or can synchronise instead of interleave. Recently, partial derivative and position based automata for regular expressions with synchronised shuffle operators were introduced. In this paper, using the framework of analytic combinatorics, we study the asymptotic average state complexity of partial derivative automata for regular expressions with strongly and arbitrarily synchronised shuffles. The new results extend and improve the ones previously obtained for regular expressions with shuffle and intersection, as these operations can be seen as special cases of synchronised shuffles. For intersection, asymptotically the average state complexity of the partial derivative automaton is [Formula: see text], which significantly improves the known exponential upper-bound.<\/jats:p>","DOI":"10.1142\/s0129054126410017","type":"journal-article","created":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T14:56:26Z","timestamp":1769093786000},"page":"269-289","source":"Crossref","is-referenced-by-count":0,"title":["Average State Complexity of Partial Derivative Automata for Synchronised Shuffles"],"prefix":"10.1142","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3798-9348","authenticated-orcid":false,"given":"Sabine","family":"Broda","sequence":"first","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-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":[[2026,1,21]]},"reference":[{"key":"S0129054126410017BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"issue":"1","key":"S0129054126410017BIB002","first-page":"5","volume":"22","author":"Bastos R.","year":"2017","journal-title":"J. Autom. Lang. Comb."},{"key":"S0129054126410017BIB003","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054112400400"},{"key":"S0129054126410017BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.08.013"},{"key":"S0129054126410017BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/3388392.3388401"},{"key":"S0129054126410017BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-40247-0_7"},{"key":"S0129054126410017BIB007","volume":"133","author":"Broda S.","year":"2023","journal-title":"J. Log. Algebr. Methods Program."},{"key":"S0129054126410017BIB008","doi-asserted-by":"publisher","DOI":"10.3233\/FUN-2001-45303"},{"key":"S0129054126410017BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00267-5"},{"key":"S0129054126410017BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16721-3_11"},{"key":"S0129054126410017BIB011","volume-title":"Analytic Combinatorics","author":"Flajolet P.","year":"2008"},{"key":"S0129054126410017BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-38919-2_15"},{"key":"S0129054126410017BIB013","first-page":"51\u201457","volume":"5","author":"Mirkin B. G.","year":"1966","journal-title":"Engineering Cybernetics"},{"key":"S0129054126410017BIB014","series-title":"LNCS","first-page":"626","volume-title":"Proc. 3rd LATA","volume":"5457","author":"Nicaud C.","year":"2009"},{"key":"S0129054126410017BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.11.010"},{"key":"S0129054126410017BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.04.007"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054126410017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T05:37:07Z","timestamp":1770961027000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054126410017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1]]},"references-count":16,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1142\/S0129054126410017"],"URL":"https:\/\/doi.org\/10.1142\/s0129054126410017","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1]]}}}