{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T15:54:22Z","timestamp":1713455662861},"reference-count":14,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02n03","funder":[{"name":"Netherlands Organisation of Scientific Research","award":["016.Veni.192.103"],"award-info":[{"award-number":["016.Veni.192.103"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:p> Paren<jats:sub>n<\/jats:sub> is the typical generalization of the Dyck language to multiple types of parentheses. We generalize its notion of balancedness to allow parentheses of different types to freely commute. We show that balanced regular and [Formula: see text]-regular languages can be characterized by syntactic constraints on regular and [Formula: see text]-regular expressions and, using the shuffle on trajectories operator, we define grammars for balanced-by-construction expressions with which one can express every balanced regular and [Formula: see text]-regular language. <\/jats:p>","DOI":"10.1142\/s0129054122440026","type":"journal-article","created":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T09:27:23Z","timestamp":1669195643000},"page":"117-144","source":"Crossref","is-referenced-by-count":1,"title":["Balanced-by-Construction Regular and \u03c9-Regular Languages"],"prefix":"10.1142","volume":"34","author":[{"given":"Luc","family":"Edixhoven","sequence":"first","affiliation":[{"name":"Department of Computer Science, Open University, The Netherlands"},{"name":"Centrum Wiskunde & Informatica (CWI), The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sung-Shik","family":"Jongmans","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Open University, The Netherlands"},{"name":"Centrum Wiskunde & Informatica (CWI), The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,11,22]]},"reference":[{"key":"S0129054122440026BIB001","series-title":"Studies in Logic and the Foundations of Mathematics","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/S0049-237X(09)70104-1","volume-title":"Computer Programming and Formal Systems","volume":"26","author":"Chomsky N.","year":"1959"},{"issue":"4","key":"S0129054122440026BIB002","first-page":"349","volume":"59","author":"Domaratzki M.","year":"2004","journal-title":"Fundam. Informaticae"},{"issue":"1","key":"S0129054122440026BIB003","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0012-365X(00)00150-3","volume":"225","author":"Duchon P.","year":"2000","journal-title":"Discret. Math."},{"key":"S0129054122440026BIB004","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1007\/978-3-030-81508-0_11","volume-title":"DLT","volume":"12811","author":"Edixhoven L.","year":"2021"},{"issue":"4","key":"S0129054122440026BIB006","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/S0022-0000(71)80023-5","volume":"5","author":"Gruska J.","year":"1971","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"S0129054122440026BIB007","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0012-365X(90)90039-K","volume":"82","author":"Labelle J.","year":"1990","journal-title":"Discret. Math."},{"issue":"4","key":"S0129054122440026BIB008","doi-asserted-by":"crossref","first-page":"880","DOI":"10.1137\/S0097539701394493","volume":"32","author":"Liebehenschel J.","year":"2003","journal-title":"SIAM J. Comput."},{"issue":"1","key":"S0129054122440026BIB009","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1080\/00207169908804878","volume":"73","author":"Mart\u00edn-Vide C.","year":"1999","journal-title":"Int. J. Comput. Math."},{"issue":"1","key":"S0129054122440026BIB010","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00163-1","volume":"197","author":"Mateescu A.","year":"1998","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"S0129054122440026BIB011","first-page":"145","volume":"5","author":"Mateescu A.","year":"2000","journal-title":"J. Autom. Lang. Comb."},{"key":"S0129054122440026BIB012","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/978-3-642-54789-8_16","volume-title":"Categories and Types in Logic, Language, and Physics","volume":"8222","author":"Moortgat M.","year":"2014"},{"key":"S0129054122440026BIB013","first-page":"3","volume-title":"SWCT","author":"Muller D. E.","year":"1963"},{"issue":"1","key":"S0129054122440026BIB014","first-page":"341","volume":"64","author":"Okhotin A.","year":"2005","journal-title":"Fundam. Informaticae"},{"issue":"3","key":"S0129054122440026BIB015","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0012-365X(79)90134-1","volume":"28","author":"Prodinger H.","year":"1979","journal-title":"Discret. Math."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122440026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,20]],"date-time":"2023-03-20T07:52:56Z","timestamp":1679298776000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122440026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,22]]},"references-count":14,"journal-issue":{"issue":"02n03","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10.1142\/S0129054122440026"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122440026","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,22]]}}}