{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:46:17Z","timestamp":1757454377500},"reference-count":29,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p> Techniques are developed for creating new and general language families of only semilinear languages, and for showing families only contain semilinear languages. It is shown that for language families [Formula: see text] that are semilinear full trios, the smallest full AFL containing [Formula: see text] that is also closed under intersection with languages in [Formula: see text] (where [Formula: see text] is the family of languages accepted by [Formula: see text]s augmented with reversal-bounded counters), is also semilinear. If these closure properties are effective, this also immediately implies decidability of membership, emptiness, and infiniteness for these general families. From the general techniques, new grammar systems are given that are extensions of well-known families of semilinear full trios, whereby it is implied that these extensions must only describe semilinear languages. This also implies positive decidability properties for the new systems. Some characterizations of the new families are also given. <\/jats:p>","DOI":"10.1142\/s0129054120420095","type":"journal-article","created":{"date-parts":[[2020,12,29]],"date-time":"2020-12-29T01:59:04Z","timestamp":1609207144000},"page":"1179-1198","source":"Crossref","is-referenced-by-count":5,"title":["Semilinearity of Families of Languages"],"prefix":"10.1142","volume":"31","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, CA 93106, USA"}]},{"given":"Ian","family":"McQuillan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Saskatchewan Saskatoon, SK S7N 5A9, Canada"}]}],"member":"219","published-online":{"date-parts":[[2020,12,28]]},"reference":[{"issue":"4","key":"S0129054120420095BIB001","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"Aho A. V.","year":"1968","journal-title":"J. ACM"},{"key":"S0129054120420095BIB002","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054196000191"},{"issue":"1","key":"S0129054120420095BIB004","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.tcs.2006.01.037","volume":"356","author":"D\u2019Alessandro F.","year":"2006","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054120420095BIB005","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/10722167_9","volume-title":"Computer Aided Verification: 12th International Conference, CAV 2000, Chicago, IL, USA, July 15\u201319, 2000. Proceedings","author":"Dang Z.","year":"2000"},{"issue":"1","key":"S0129054120420095BIB006","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0304-3975(84)90023-9","volume":"32","author":"Duske J.","year":"1984","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054120420095BIB007","volume-title":"Algebraic and Automata-Theoretic Properties of Formal Languages","author":"Ginsburg S.","year":"1975"},{"key":"S0129054120420095BIB008","volume-title":"The Mathematical Theory of Context-Free Languages","author":"Ginsburg S.","year":"1966"},{"issue":"4","key":"S0129054120420095BIB009","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0022-0000(71)80024-7","volume":"5","author":"Ginsburg S.","year":"1971","journal-title":"J. Comput. Syst. Sci."},{"key":"S0129054120420095BIB010","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/978-3-642-31424-7_22","volume-title":"Computer Aided Verification: 24th International Conference, CAV 2012, Berkeley, CA, USA, July 7\u201313, 2012, Proceedings","author":"Hague M.","year":"2012"},{"key":"S0129054120420095BIB011","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/978-3-319-45994-3_11","volume-title":"Reachability Problems: 10th International Workshop, RP 2016, Aalborg, Denmark, September 19\u201321, 2016, Proceedings","author":"Hague M.","year":"2016"},{"key":"S0129054120420095BIB012","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1007\/978-3-642-22110-1_60","volume-title":"Computer Aided Verification","volume":"6806","author":"Hague M.","year":"2011"},{"issue":"2","key":"S0129054120420095BIB013","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1006\/jcss.2002.1836","volume":"65","author":"Harju T.","year":"2002","journal-title":"J. Comput. Syst. Sci."},{"key":"S0129054120420095BIB014","volume-title":"Introduction to Formal Language Theory","author":"Harrison M.","year":"1978"},{"key":"S0129054120420095BIB015","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/3-540-45061-0_40","volume-title":"Automata, Languages and Programming: 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30\u2013July 4, 2003, Proceedings","author":"Holzer M.","year":"2003"},{"key":"S0129054120420095BIB016","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S0129054120420095BIB018","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-319-94812-6_18","volume-title":"23rd Int. Conf. Implementation and Application of Automata, CIAA 2018","volume":"10977","author":"Ibarra O.","year":"2018"},{"issue":"1","key":"S0129054120420095BIB019","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"Ibarra O. H.","year":"1978","journal-title":"J. ACM"},{"key":"S0129054120420095BIB020","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/3-540-44618-4_15","volume-title":"CONCUR 2000 \u2014 Concurrency Theory: 11th International Conference University Park, PA, USA, August 22\u201325, 2000 Proceedings","author":"Ibarra O. H.","year":"2000"},{"key":"S0129054120420095BIB021","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054101000898"},{"issue":"1","key":"S0129054120420095BIB022","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1016\/S0304-3975(02)00545-5","volume":"299","author":"Ibarra O. H.","year":"2003","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054120420095BIB023","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.tcs.2016.02.034","volume":"627","author":"Ibarra O. H.","year":"2016","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054120420095BIB024","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2018.04.024","volume":"738","author":"Ibarra O. H.","year":"2018","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"S0129054120420095BIB025","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0304-3975(01)00268-7","volume":"289","author":"Ibarra O. H.","year":"2002","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054120420095BIB026","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/3-540-44612-5_38","volume-title":"Mathematical Foundations of Computer Science 2000: 25th International Symposium, MFCS 2000, Bratislava, Slovakia, August 28\u2013September 1, 2000 Proceedings","author":"Ibarra O. H.","year":"2000"},{"issue":"3","key":"S0129054120420095BIB027","doi-asserted-by":"crossref","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"Minsky M. L.","year":"1961","journal-title":"Ann. Math."},{"key":"S0129054120420095BIB028","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"Parikh R.","year":"1966","journal-title":"J. ACM"},{"key":"S0129054120420095BIB029","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0019-9958(78)90050-5","volume":"38","author":"Rozenberg G.","year":"1978","journal-title":"Information and Control"},{"key":"S0129054120420095BIB030","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139195218","volume-title":"Elements of Automata Theory","author":"Sakarovitch J.","year":"2009"},{"key":"S0129054120420095BIB031","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1007\/978-3-662-47666-6_35","volume-title":"Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015","volume":"9135","author":"Zetzsche G.","year":"2015"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120420095","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T03:33:28Z","timestamp":1611200008000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120420095"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":29,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.1142\/S0129054120420095"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120420095","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}