{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:21Z","timestamp":1759637661010,"version":"3.41.0"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>We study the state complexity of catenation combined with symmetric difference. First, an upper bound is computed using some combinatoric tools. Then, this bound is shown to be tight by giving a witness for it. Moreover, we relate this work with the study of state complexity for two other combinations: catenation with union and catenation with intersection. We extract a unified approach which allows to obtain the state complexity of any combination involving catenation and a binary boolean operation.<\/jats:p>","DOI":"10.1142\/s0129054116500234","type":"journal-article","created":{"date-parts":[[2016,11,15]],"date-time":"2016-11-15T08:52:57Z","timestamp":1479199977000},"page":"675-703","source":"Crossref","is-referenced-by-count":5,"title":["State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach"],"prefix":"10.1142","volume":"27","author":[{"given":"Pascal","family":"Caron","sequence":"first","affiliation":[{"name":"LITIS, Universit\u00e9 de Rouen, 76801 Saint-\u00c9tienne du Rouvray Cedex, France"}]},{"given":"Jean-Gabriel","family":"Luque","sequence":"additional","affiliation":[{"name":"LITIS, Universit\u00e9 de Rouen, 76801 Saint-\u00c9tienne du Rouvray Cedex, France"}]},{"given":"Ludovic","family":"Mignot","sequence":"additional","affiliation":[{"name":"LITIS, Universit\u00e9 de Rouen, 76801 Saint-\u00c9tienne du Rouvray Cedex, France"}]},{"given":"Bruno","family":"Patrou","sequence":"additional","affiliation":[{"name":"LITIS, Universit\u00e9 de Rouen, 76801 Saint-\u00c9tienne du Rouvray Cedex, France"}]}],"member":"219","published-online":{"date-parts":[[2016,11,15]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054113400133"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111009045"},{"issue":"1","key":"p_8","first-page":"75","volume":"83","author":"Gao Y.","year":"2008","journal-title":"Fundam. Inform."},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003133"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.04.011"},{"issue":"2","key":"p_12","doi-asserted-by":"crossref","first-page":"161","DOI":"10.3233\/FI-2011-502","volume":"109","author":"Jir\u00e1skov\u00e1 G.","year":"2011","journal-title":"Fundam. Inform."},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.03.018"},{"key":"p_15","first-page":"1373","volume":"11","author":"Maslov A. N.","year":"1970","journal-title":"Soviet Math. Dokl."},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.015"},{"key":"p_21","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1080\/00150517.1969.12431145","volume":"7","author":"Uppuluri V.","year":"1969","journal-title":"Fib. Quart."},{"issue":"2","key":"p_22","first-page":"221","volume":"6","author":"Yu S.","year":"2001","journal-title":"Languages and Combinatorics"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054116500234","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T15:09:20Z","timestamp":1749740960000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054116500234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":15,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2016,11,15]]},"published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1142\/S0129054116500234"],"URL":"https:\/\/doi.org\/10.1142\/s0129054116500234","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}