{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T15:59:33Z","timestamp":1649174373642},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"06n07","funder":[{"name":"Natural Sciences and Engineering Research Council of Canada Grant","award":["2016-06172"],"award-info":[{"award-number":["2016-06172"]}]},{"DOI":"10.13039\/501100006109","name":"VEGA","doi-asserted-by":"crossref","award":["2\/0084\/15"],"award-info":[{"award-number":["2\/0084\/15"]}],"id":[{"id":"10.13039\/501100006109","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005357","name":"APVV","doi-asserted-by":"crossref","award":["15-0091"],"award-info":[{"award-number":["15-0091"]}],"id":[{"id":"10.13039\/501100005357","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100006109","name":"VEGA","doi-asserted-by":"crossref","award":["1\/0142\/15"],"award-info":[{"award-number":["1\/0142\/15"]}],"id":[{"id":"10.13039\/501100006109","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005357","name":"APVV","doi-asserted-by":"crossref","award":["15-0091"],"award-info":[{"award-number":["15-0091"]}],"id":[{"id":"10.13039\/501100005357","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:p> We study Kuratowski algebras generated by prefix-, suffix-, factor-, and subword-free languages under the operations of star and complementation. We examine 12 possible algebras, and for each of them, we decide whether or not it can be generated by a prefix-, suffix-, factor-, or subword-free language. In each case when an algebra can be generated by such a language, we show that this language can be taken to be regular, and we compute upper bounds on the state complexities of all the generated languages. Finally, we find generators that maximize these complexities. <\/jats:p>","DOI":"10.1142\/s0129054119400306","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:06:43Z","timestamp":1568876803000},"page":"1091-1115","source":"Crossref","is-referenced-by-count":0,"title":["Kuratowski Algebras Generated by Prefix-, Suffix-, Factor-, and Subword-Free Languages Under Star and Complementation"],"prefix":"10.1142","volume":"30","author":[{"suffix":"Jr.","given":"Jozef","family":"Jir\u00e1sek","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Saskatchewan, 110 Science Place, Saskatoon, SK S7N 5C9, Canada"}]},{"given":"Mat\u00fa\u0161","family":"Palmovsk\u00fd","sequence":"additional","affiliation":[{"name":"Mathematical Institute, Slovak Academy of Sciences, Gre\u0161\u00e1kova 6, 040 01 Ko\u0161ice, Slovakia"}]},{"given":"Juraj","family":"\u0160ebej","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Faculty of Science, P. J. \u0160af\u00e1rik University, Jesenn\u00e1 5, 040 01 Ko\u0161ice, Slovakia"}]}],"member":"219","published-online":{"date-parts":[[2019,9,19]]},"reference":[{"key":"S0129054119400306BIB001","author":"Brzozowski J. A.","year":"2016","journal-title":"Personal Communication"},{"key":"S0129054119400306BIB002","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111008052"},{"key":"S0129054119400306BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41114-9_6"},{"key":"S0129054119400306BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9515-7"},{"key":"S0129054119400306BIB005","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/978-3-642-25929-6_9","volume-title":"Mathematical and Engineering Methods in Computer Science - 7th International Doctoral Workshop, MEMICS 2011","volume":"7119","author":"Cmorik R.","year":"2011"},{"key":"S0129054119400306BIB006","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054115500392"},{"key":"S0129054119400306BIB007","doi-asserted-by":"publisher","DOI":"10.1080\/0025570X.1991.11977605"},{"key":"S0129054119400306BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.054"},{"key":"S0129054119400306BIB009","first-page":"99","volume-title":"Automata, Formal Languages, and Related Topics","author":"Han Y.","year":"2009"},{"key":"S0129054119400306BIB010","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S0129054119400306BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38536-0_22"},{"key":"S0129054119400306BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21500-6_24"},{"key":"S0129054119400306BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-60252-3_15"},{"key":"S0129054119400306BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40946-7_13"},{"key":"S0129054119400306BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08846-4_17"},{"key":"S0129054119400306BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31653-1_34"},{"key":"S0129054119400306BIB017","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/978-3-642-25929-6_11","volume-title":"Mathematical and Engineering Methods in Computer Science - 7th International Doctoral Workshop, MEMICS 2011","volume":"7119","author":"Krausov\u00e1 M.","year":"2011"},{"key":"S0129054119400306BIB018","doi-asserted-by":"publisher","DOI":"10.4064\/fm-3-1-182-199"},{"key":"S0129054119400306BIB019","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2016024"},{"key":"S0129054119400306BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19225-3_20"},{"key":"S0129054119400306BIB021","volume-title":"Introduction to the Theory of Computation","author":"Sipser M.","year":"2012"},{"key":"S0129054119400306BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054119400306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:06:56Z","timestamp":1568876816000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119400306"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":22,"journal-issue":{"issue":"06n07","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.1142\/S0129054119400306"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119400306","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}