{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:01:34Z","timestamp":1743037294270,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319192246"},{"type":"electronic","value":"9783319192253"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19225-3_19","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T15:51:06Z","timestamp":1434383466000},"page":"220-230","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The State Complexity of Permutations on Finite Languages over Binary Alphabets"],"prefix":"10.1007","author":[{"given":"Alexandros","family":"Palioudakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Da-Jung","family":"Cho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Go\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yo-Sub","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sang-Ki","family":"Ko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"key":"19_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/3-540-45526-4_6","volume-title":"Automata Implementation","author":"C C\u00e2mpeanu","year":"2001","unstructured":"C\u00e2mpeanu, C., Culik, K., Salomaa, K., Yu, S.: State complexity of basic operations on finite languages. In: Boldt, O., J\u00fcrgensen, H. (eds.) WIA 1999. LNCS, vol. 2214, pp. 60\u201370. Springer, Heidelberg (2001)"},{"issue":"4","key":"19_CR2","first-page":"455","volume":"7","author":"M Domaratzki","year":"2002","unstructured":"Domaratzki, M.: State complexity of proportional removals. J. Autom. Lang. Comb. 7(4), 455\u2013468 (2002)","journal-title":"J. Autom. Lang. Comb."},{"issue":"4","key":"19_CR3","first-page":"407","volume":"10","author":"K Ellul","year":"2005","unstructured":"Ellul, K., Krawetz, B., Shallit, J., Wang, M.: Regular expressions: new results and open problems. J. Autom. Lang. Comb. 10(4), 407\u2013437 (2005)","journal-title":"J. Autom. Lang. Comb."},{"key":"19_CR4","unstructured":"Gao, Y., Moreira, N., Reis, R., Yu, S.: A review of state complexity of individual operations. Technical report, Universidade do Porto, Technical Report Series DCC-2011-08, Version 1.1, September (2012). www.dcc.fc.up.pt\/Pubs (To appear in Computer Science Review, 2015)"},{"key":"19_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-642-39310-5_11","volume-title":"Descriptional Complexity of Formal Systems","author":"D Go\u010d","year":"2013","unstructured":"Go\u010d, D., Palioudakis, A., Salomaa, K.: Nondeterministic state complexity of proportional removals. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 102\u2013111. Springer, Heidelberg (2013)"},{"issue":"2","key":"19_CR6","first-page":"193","volume":"8","author":"J Goldstine","year":"2002","unstructured":"Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. UCS 8(2), 193\u2013234 (2002)","journal-title":"J. UCS"},{"issue":"03","key":"19_CR7","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1142\/S0129054108005838","volume":"19","author":"YS Han","year":"2008","unstructured":"Han, Y.S., Salomaa, K.: State complexity of union and intersection of finite languages. Int. J. Found. Comput. Sci. 19(03), 581\u2013595 (2008)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"19_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/3-540-44977-9_14","volume-title":"Implementation and Application of Automata","author":"M Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: State complexity of basic operations on nondeterministic finite automata. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol. 2608, pp. 148\u2013157. Springer, Heidelberg (2003)"},{"issue":"3","key":"19_CR9","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.ic.2010.11.013","volume":"209","author":"M Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata \u2013 a survey. Inf. Comput. 209(3), 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"key":"19_CR10","unstructured":"Kleene, S.C.: Representation of events in nerve nets and finite automata. Technical report, DTIC Document (1951)"},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1007\/978-3-319-09704-6_26","volume-title":"Descriptional Complexity of Formal Systems","author":"GJ Lavado","year":"2014","unstructured":"Lavado, G.J., Pighizzini, G., Seki, S.: Operational state complexity under Parikh equivalence. In: J\u00fcrgensen, H., Karhum\u00e4ki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 294\u2013305. Springer, Heidelberg (2014)"},{"key":"19_CR12","first-page":"328","volume":"9","author":"O Lupanov","year":"1963","unstructured":"Lupanov, O.: A comparison of two types of finite sources. Problemy Kibernetiki 9, 328\u2013335 (1963)","journal-title":"Problemy Kibernetiki"},{"key":"19_CR13","unstructured":"Maslov, A.: Estimates of the number of states of finite automata. In: Soviet Mathematics Doklady, Translation from Doklady Akademii Nauk SSSR 194, vol. 11, pp. 1266\u20131268, 1373\u20131375 (1970)"},{"issue":"4","key":"19_CR14","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF02478259","volume":"5","author":"WS McCulloch","year":"1943","unstructured":"McCulloch, W.S., Pitts, W.: A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophys. 5(4), 115\u2013133 (1943)","journal-title":"Bull. Math. Biophys."},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: SWAT (FOCS), pp. 188\u2013191. IEEE Computer Society (1971)","DOI":"10.1109\/SWAT.1971.11"},{"issue":"10","key":"19_CR16","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"C\u201320","author":"F Moore","year":"1971","unstructured":"Moore, F.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. C\u201320(10), 1211\u20131214 (1971)","journal-title":"IEEE Trans. Comput."},{"issue":"4","key":"19_CR17","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"RJ Parikh","year":"1966","unstructured":"Parikh, R.J.: On context-free languages. J. ACM (JACM) 13(4), 570\u2013581 (1966)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"19_CR18","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.S.: Finite automata and their decision problems. IBM J. Res. Dev. 3(2), 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"19_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511808876","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"J Shallit","year":"2008","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2008)"},{"issue":"2","key":"19_CR20","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theor. Comput. Sci. 125(2), 315\u2013328 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR21","first-page":"41","volume-title":"Handbook of Formal Languages, Volume 1, Chap. Regular Languages","author":"S Yu","year":"1998","unstructured":"Yu, S.: Handbook of Formal Languages, Volume 1, Chap. Regular Languages, pp. 41\u2013110. Springer, Heidelberg (1998)"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19225-3_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T09:08:23Z","timestamp":1674205703000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19225-3_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319192246","9783319192253"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19225-3_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}