{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T08:56:12Z","timestamp":1770454572225,"version":"3.49.0"},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:p> Two finite words [Formula: see text] and [Formula: see text] are [Formula: see text]-binomially equivalent if, for each word [Formula: see text] of length at most [Formula: see text], [Formula: see text] appears the same number of times as a subsequence (i.e., as a scattered subword) of both [Formula: see text] and [Formula: see text]. This notion generalizes abelian equivalence. In this paper, we study the equivalence classes induced by the [Formula: see text]-binomial equivalence. We provide an algorithm generating the [Formula: see text]-binomial equivalence class of a word. For [Formula: see text] and alphabet of [Formula: see text] or more symbols, the language made of lexicographically least elements of every [Formula: see text]-binomial equivalence class and the language of singletons, i.e., the words whose [Formula: see text]-binomial equivalence class is restricted to a single element, are shown to be non-context-free. As a consequence of our discussions, we also prove that the submonoid generated by the generators of the free nil-[Formula: see text] group (also called free nilpotent group of class\u00a0[Formula: see text]) on [Formula: see text] generators is isomorphic to the quotient of the free monoid [Formula: see text] by the [Formula: see text]-binomial equivalence. <\/jats:p>","DOI":"10.1142\/s0218196720500459","type":"journal-article","created":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T04:57:02Z","timestamp":1589864222000},"page":"1375-1397","source":"Crossref","is-referenced-by-count":9,"title":["The binomial equivalence classes of finite words"],"prefix":"10.1142","volume":"30","author":[{"given":"Marie","family":"Lejeune","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Li\u00e8ge, All\u00e9e de la d\u00e9couverte 12 (B37), Li\u00e8ge B-4000, Belgium"}]},{"given":"Michel","family":"Rigo","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Li\u00e8ge, All\u00e9e de la d\u00e9couverte 12 (B37), Li\u00e8ge B-4000, Belgium"}]},{"given":"Matthieu","family":"Rosenfeld","sequence":"additional","affiliation":[{"name":"LIS UMR 7020 CNRS\/AMU\/UTLN, Aix Marseille Universit\u00e9 \u2014 Campus de Luminy, 163 Avenue de Luminy \u2014 case 901, BP 5, 13288 Marseille Cedex 9, France"}]}],"member":"219","published-online":{"date-parts":[[2020,7,14]]},"reference":[{"key":"S0218196720500459BIB001","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2017-1553"},{"key":"S0218196720500459BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.06.011"},{"key":"S0218196720500459BIB003","first-page":"239","volume-title":"Multidisciplinary Creativity: Homage to Gheorghe Paun on his th Birthday","author":"Freydenberger D. D.","year":"2015"},{"key":"S0218196720500459BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85780-8_27"},{"key":"S0218196720500459BIB005","first-page":"333","volume":"113","author":"Ginsburg S.","year":"1964","journal-title":"Trans. Amer. Math. Soc."},{"key":"S0218196720500459BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00152-3"},{"key":"S0218196720500459BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(80)90493-3"},{"key":"S0218196720500459BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.06.010"},{"key":"S0218196720500459BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2013.08.008"},{"key":"S0218196720500459BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09698-8_18"},{"key":"S0218196720500459BIB012","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2001131"},{"key":"S0218196720500459BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.07.025"},{"key":"S0218196720500459BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.036"},{"key":"S0218196720500459BIB015","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0046"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196720500459","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,8]],"date-time":"2020-10-08T10:29:53Z","timestamp":1602152993000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196720500459"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,14]]},"references-count":14,"journal-issue":{"issue":"07","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["10.1142\/S0218196720500459"],"URL":"https:\/\/doi.org\/10.1142\/s0218196720500459","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,14]]}}}