{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:09:21Z","timestamp":1767236961967},"reference-count":21,"publisher":"World Scientific Pub Co Pte Lt","issue":"06n07","funder":[{"DOI":"10.13039\/501100006753","name":"CMUP","doi-asserted-by":"crossref","award":["UID\/MAT\/00144\/2013"],"award-info":[{"award-number":["UID\/MAT\/00144\/2013"]}],"id":[{"id":"10.13039\/501100006753","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:p> For regular expressions in (strong) star normal form a large set of efficient algorithms is known, from conversions into finite automata to characterisations of unambiguity. In this paper we study the average complexity of this class of expressions using analytic combinatorics. As it is not always feasible to obtain explicit expressions for the generating functions involved, here we show how to get the required information for the asymptotic estimates with an indirect use of the existence of Puiseux expansions at singularities. We study, asymptotically and on average, the alphabetic size, the size of the [Formula: see text]-follow automaton and of the position automaton, as well as the ratio and the size of these expressions to standard regular expressions. <\/jats:p>","DOI":"10.1142\/s0129054119400227","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T03:06:43Z","timestamp":1568862403000},"page":"899-920","source":"Crossref","is-referenced-by-count":9,"title":["On Average Behaviour of Regular Expressions in Strong Star Normal Form"],"prefix":"10.1142","volume":"30","author":[{"given":"Sabine","family":"Broda","sequence":"first","affiliation":[{"name":"CMUP &amp; DM-DCC, Faculdade de Ci\u00eancias da Universidade do Porto, Rua do Campo Alegre, 4169-007 Porto, Portugal"}]},{"given":"Ant\u00f3nio","family":"Machiavelo","sequence":"additional","affiliation":[{"name":"CMUP &amp; DM-DCC, Faculdade de Ci\u00eancias da Universidade do Porto, Rua do Campo Alegre, 4169-007 Porto, Portugal"}]},{"given":"Nelma","family":"Moreira","sequence":"additional","affiliation":[{"name":"CMUP &amp; DM-DCC, Faculdade de Ci\u00eancias da Universidade do Porto, Rua do Campo Alegre, 4169-007 Porto, Portugal"}]},{"given":"Rog\u00e9rio","family":"Reis","sequence":"additional","affiliation":[{"name":"CMUP &amp; DM-DCC, Faculdade de Ci\u00eancias da Universidade do Porto, Rua do Campo Alegre, 4169-007 Porto, Portugal"}]}],"member":"219","published-online":{"date-parts":[[2019,9,19]]},"reference":[{"key":"S0129054119400227BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"S0129054119400227BIB002","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111008908"},{"key":"S0129054119400227BIB003","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054112400400"},{"key":"S0129054119400227BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.02.013"},{"key":"S0129054119400227BIB005","first-page":"167","volume":"116","author":"Broda S.","year":"2015","journal-title":"BEATCS"},{"key":"S0129054119400227BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-60252-3_6"},{"key":"S0129054119400227BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90287-4"},{"key":"S0129054119400227BIB008","doi-asserted-by":"publisher","DOI":"10.1142\/S021819670700355X"},{"key":"S0129054119400227BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00267-5"},{"key":"S0129054119400227BIB010","volume-title":"Analytic Combinatorics","author":"Flajolet P.","year":"2008"},{"key":"S0129054119400227BIB011","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"S0129054119400227BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13089-2_24"},{"key":"S0129054119400227BIB014","first-page":"46","volume-title":"Proc. SOFSEM 2008","author":"Gulan S.","year":"2008"},{"key":"S0129054119400227BIB015","volume-title":"Analytic Function Theory","author":"Hille E.","year":"1962"},{"key":"S0129054119400227BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00090-7"},{"key":"S0129054119400227BIB017","series-title":"Grad. Texts in Math.","volume-title":"Algebra","volume":"211","author":"Lang S.","year":"2001","edition":"3"},{"key":"S0129054119400227BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00982-2_53"},{"key":"S0129054119400227BIB019","doi-asserted-by":"publisher","DOI":"10.1145\/321088.321097"},{"key":"S0129054119400227BIB021","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195218"},{"key":"S0129054119400227BIB022","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"S0129054119400227BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054119400227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T03:07:23Z","timestamp":1568862443000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119400227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":21,"journal-issue":{"issue":"06n07","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.1142\/S0129054119400227"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119400227","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}