{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:29:12Z","timestamp":1747189752775,"version":"3.40.5"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p> We consider the problem of partitioning effectively a given irreflexive (and possibly symmetric) rational relation [Formula: see text] into two asymmetric rational relations. This problem is motivated by a recent method of embedding an [Formula: see text]-independent language into one that is maximal [Formula: see text]-independent, where the method requires to use an asymmetric partition of [Formula: see text]. We solve the problem when [Formula: see text] is length-separable, which means that the following two subsets of [Formula: see text] are rational: the subset of word pairs [Formula: see text] where [Formula: see text]; and the subset of word pairs [Formula: see text] where [Formula: see text]. This property is satisfied by all recognizable, all left synchronous, and all right synchronous relations. We leave it as an open problem when [Formula: see text] is not length-separable. We also define zero-avoiding transducers for length-separable relations, which makes our partitioning solution constructive. <\/jats:p>","DOI":"10.1142\/s0129054121410033","type":"journal-article","created":{"date-parts":[[2021,2,7]],"date-time":"2021-02-07T15:47:23Z","timestamp":1612712843000},"page":"455-480","source":"Crossref","is-referenced-by-count":0,"title":["Zero-Avoiding Transducers, Length Separable Relations, and the Rational Asymmetric Partition Problem"],"prefix":"10.1142","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6628-067X","authenticated-orcid":false,"given":"Stavros","family":"Konstantinidis","sequence":"first","affiliation":[{"name":"Mathematics and Computing Science, Saint Mary\u2019s University, 923 Robie Str., Halifax, Nova Scotia B3H 3C3, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mitja","family":"Mastnak","sequence":"additional","affiliation":[{"name":"Mathematics and Computing Science, Saint Mary\u2019s University, 923 Robie Str., Halifax, Nova Scotia B3H 3C3, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juraj","family":"\u0160ebej","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Faculty of Science, P. J. \u0160af\u00e1rik University, Ko\u0161ice, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2021,2,6]]},"reference":[{"key":"S0129054121410033BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"S0129054121410033BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02737-6_13"},{"key":"S0129054121410033BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.011"},{"key":"S0129054121410033BIB004","first-page":"159","volume":"89","author":"Choffrut C.","year":"2006","journal-title":"Bull. EATCS"},{"key":"S0129054121410033BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00371-9"},{"volume-title":"Introduction to Automata Theory, Languages, and Computation","year":"1979","author":"Hopcroft J. E.","key":"S0129054121410033BIB006"},{"key":"S0129054121410033BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-23679-3_14"},{"issue":"4","key":"S0129054121410033BIB008","first-page":"311","volume":"21","author":"Konstantinidis S.","year":"2016","journal-title":"J. Autom. Lang. Comb."},{"key":"S0129054121410033BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-60252-3_4"},{"volume-title":"Handbook of Formal Languages, Vol. I","year":"1997","author":"Rozenberg G.","key":"S0129054121410033BIB010"},{"key":"S0129054121410033BIB011","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195218"},{"key":"S0129054121410033BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0087133"},{"volume-title":"Languages and Codes","year":"2005","author":"Yu S. S.","key":"S0129054121410033BIB015"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054121410033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T01:45:02Z","timestamp":1628732702000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054121410033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,6]]},"references-count":13,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1142\/S0129054121410033"],"URL":"https:\/\/doi.org\/10.1142\/s0129054121410033","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2021,2,6]]}}}