{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,26]],"date-time":"2024-07-26T09:50:51Z","timestamp":1721987451867},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,2]]},"abstract":"<jats:p> Rational relations are binary relations of finite words that are realised by non-deterministic finite state transducers (NFT). A multi-sequential relation is a rational relation which is equal to a finite union of (graphs) of partial sequential functions, i.e. functions realised by input-deterministic transducers. <\/jats:p><jats:p> The particular case of multi-sequential functions was studied by Choffrut and Sch\u00fctzenberger who proved that given a rational function (as a transducer), it is decidable whether it is multi-sequential. Their procedure is based on an effective characterisation of unambiguous transducers that do not define multi-sequential functions, that we call the fork property. <\/jats:p><jats:p> In this paper, we show that the fork property also characterises the class of transducers that do not define multi-sequential relations. Moreover, we prove that the fork property can be decided in PTime. This leads to a PTime procedure which, given a transducer, decides whether it defines a multi-sequential relation. <\/jats:p>","DOI":"10.1142\/s0129054118400075","type":"journal-article","created":{"date-parts":[[2018,4,11]],"date-time":"2018-04-11T03:34:45Z","timestamp":1523417685000},"page":"271-295","source":"Crossref","is-referenced-by-count":3,"title":["Multi-Sequential Word Relations"],"prefix":"10.1142","volume":"29","author":[{"given":"Isma\u00ebl","family":"Jecker","sequence":"first","affiliation":[{"name":"Computer Science Department, Universit\u00e9 Libre de Bruxelles, Bd de la Plaine 1050, Brussels, Belgium"}]},{"given":"Emmanuel","family":"Filiot","sequence":"additional","affiliation":[{"name":"Computer Science Department, Universit\u00e9 Libre de Bruxelles, Bd de la Plaine 1050, Brussels, Belgium"}]}],"member":"219","published-online":{"date-parts":[[2018,4,11]]},"reference":[{"key":"S0129054118400075BIB001","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002126"},{"key":"S0129054118400075BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00271-7"},{"key":"S0129054118400075BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00214-6"},{"key":"S0129054118400075BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90049-4"},{"key":"S0129054118400075BIB010","doi-asserted-by":"publisher","DOI":"10.1147\/rd.91.0047"},{"key":"S0129054118400075BIB011","doi-asserted-by":"publisher","DOI":"10.1145\/321466.321473"},{"issue":"1","key":"S0129054118400075BIB012","first-page":"61","volume":"16","author":"Gurari E. M.","year":"1983","journal-title":"Theory Comput. Syst."},{"key":"S0129054118400075BIB013","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322058"},{"key":"S0129054118400075BIB014","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195218"},{"key":"S0129054118400075BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9206-6"},{"key":"S0129054118400075BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-07407-4_22"},{"issue":"8","key":"S0129054118400075BIB017","first-page":"749","volume":"27","author":"Weber A.","year":"1989","journal-title":"Acta Informatica"},{"key":"S0129054118400075BIB018","doi-asserted-by":"publisher","DOI":"10.1137\/0222014"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118400075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T08:27:42Z","timestamp":1565166462000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118400075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2]]},"references-count":13,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2018,4,11]]},"published-print":{"date-parts":[[2018,2]]}},"alternative-id":["10.1142\/S0129054118400075"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118400075","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2]]}}}