{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T14:28:01Z","timestamp":1773498481133,"version":"3.50.1"},"reference-count":23,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>Sequences (L<jats:sub>n<\/jats:sub>| n \u2265 k), called streams, of regular languages L<jats:sub>n<\/jats:sub>are considered, where k is some small positive integer, n is the state complexity of L<jats:sub>n<\/jats:sub>, and the languages in a stream differ only in the parameter n, but otherwise, have the same properties. The following measures of complexity are proposed for any stream: (1) the state complexity n of L<jats:sub>n<\/jats:sub>, that is, the number of left quotients of L<jats:sub>n<\/jats:sub>(used as a reference); (2) the state complexities of the left quotients of L<jats:sub>n<\/jats:sub>; (3) the number of atoms of L<jats:sub>n<\/jats:sub>; (4) the state complexities of the atoms of L<jats:sub>n<\/jats:sub>; (5) the size of the syntactic semigroup of L<jats:sub>n<\/jats:sub>; and the state complexities of the following operations: (6) the reverse of L<jats:sub>n<\/jats:sub>; (7) the star of L<jats:sub>n<\/jats:sub>; (8) union, intersection, difference and symmetric difference of L<jats:sub>m<\/jats:sub>and L<jats:sub>n<\/jats:sub>; and (9) the concatenation of L<jats:sub>m<\/jats:sub>and L<jats:sub>n<\/jats:sub>. A stream that has the highest possible complexity with respect to these measures is then viewed as a most complex stream. The language stream (U<jats:sub>n<\/jats:sub>(a, b, c) | n \u2265 3) is defined by the deterministic finite automaton with state set {0, 1, \u2026 , n\u22121}, initial state 0, set {n\u22121} of final states, and input alphabet {a, b, c}, where a performs a cyclic permutation of the n states, b transposes states 0 and 1, and c maps state n \u2212 1 to state 0. This stream achieves the highest possible complexities with the exception of boolean operations where m = n. In the latter case, one can use U<jats:sub>n<\/jats:sub>(a, b, c) and U<jats:sub>n<\/jats:sub>(b, a, c), where the roles of a and b are interchanged in the second language. In this sense, U<jats:sub>n<\/jats:sub>(a, b, c) is a universal witness. This witness and its extensions also apply to a large number of combined regular operations.<\/jats:p>","DOI":"10.1142\/s0129054113400133","type":"journal-article","created":{"date-parts":[[2013,12,27]],"date-time":"2013-12-27T08:17:54Z","timestamp":1388132274000},"page":"691-708","source":"Crossref","is-referenced-by-count":35,"title":["IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES"],"prefix":"10.1142","volume":"24","author":[{"given":"JANUSZ","family":"BRZOZOWSKI","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2013,12,27]]},"reference":[{"issue":"1","key":"p_1","first-page":"71","volume":"15","author":"Brzozowski J.","year":"2010","journal-title":"J. Autom. Lang. Comb."},{"key":"p_2","first-page":"5","volume":"7381","author":"Brzozowski J.","year":"2012","journal-title":"N. Moreira and R. Reis LNCS"},{"key":"p_4","first-page":"72","volume":"7982","author":"Brzozowski J.","year":"2013","journal-title":"S. Konstantinidis LNCS"},{"key":"p_5","first-page":"30","volume":"8031","author":"Brzozowski J.","year":"2013","journal-title":"H. J\u00fcrgensen and R. Reis LNCS"},{"key":"p_6","first-page":"105","volume":"6795","author":"Brzozowski J.","year":"2011","journal-title":"G. Mauri and A. Leporati LNCS"},{"key":"p_7","first-page":"50","volume":"7410","author":"Brzozowski J.","year":"2012","journal-title":"H.-C. Yen and O. H. Ibarra LNCS"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.030"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054112400047"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.028"},{"issue":"1","key":"p_11","first-page":"75","volume":"83","author":"Gao Y.","year":"2008","journal-title":"Fund. Inform."},{"key":"p_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/FI-2012-663","volume":"116","author":"Gao Y.","year":"2012","journal-title":"Fund. Inform."},{"key":"p_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/FI-2011-427","volume":"109","author":"Jir\u00e1skov\u00e1 G.","year":"2011","journal-title":"Fund. Inform."},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.03.018"},{"key":"p_15","first-page":"321","volume":"9","author":"Lupanov O. B.","year":"1963","journal-title":"Problemy Kibernetiki"},{"key":"p_16","first-page":"1266","volume":"194","author":"Maslov A. N.","year":"1970","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"p_17","first-page":"7","volume":"2","author":"Mirkin B. G.","year":"1966","journal-title":"Kibernetika (Kiev)"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223108"},{"key":"p_19","first-page":"57","author":"Myhill J.","year":"1957","journal-title":"Wright Air Development Center Technical Report"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.015"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.02.032"},{"key":"p_26","first-page":"221","volume":"6","author":"Yu S.","year":"2001","journal-title":"J. Autom. Lang. Comb."},{"key":"p_27","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\/S0129054113400133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T23:08:07Z","timestamp":1597273687000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113400133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":23,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2013,12,27]]},"published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1142\/S0129054113400133"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113400133","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}