{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T03:36:38Z","timestamp":1742960198693,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642225994"},{"type":"electronic","value":"9783642226007"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22600-7_8","type":"book-chapter","created":{"date-parts":[[2011,7,19]],"date-time":"2011-07-19T20:58:15Z","timestamp":1311109095000},"page":"93-106","source":"Crossref","is-referenced-by-count":1,"title":["Syntactic Complexity of Prefix-, Suffix-, and Bifix-Free Regular Languages"],"prefix":"10.1007","author":[{"given":"Janusz","family":"Brzozowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baiyu","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuli","family":"Ye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","volume-title":"Codes and Automata (Encyclopedia of Mathematics and its Applications)","author":"J. Berstel","year":"2009","unstructured":"Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata (Encyclopedia of Mathematics and its Applications). Cambridge University Press, Cambridge (2009)"},{"key":"8_CR2","unstructured":"Brzozowski, J.: Quotient complexity of regular languages. In: Dassow, J., Pighizzini, G., Truthe, B. (eds.) Proceedings of the 11th International Workshop on Descriptional Complexity of Formal Systems (DFS), Magdeburg, Germany, Otto-von-Guericke-Universit\u00e4t, pp. 25\u201342 (2009); to appear, J. Autom. Lang. Comb., Extended abstract at \n                    \n                      http:\/\/arxiv.org\/abs\/0907.4547"},{"key":"8_CR3","unstructured":"Brzozowski, J., Jir\u00e1skov\u00e1, G., Li, B., Smith, J.: Quotient complexity of bifix-, factor-, and subword-free regular languages. In: Proceedings of the 13th International Conference on Automata and Formal Languages, AFL (to appear, 2011), Full paper at \n                    \n                      http:\/\/arxiv.org\/abs\/1006.4843v3"},{"key":"8_CR4","series-title":"LNCS","volume-title":"Proceedings of the 15th International Conference on Developments in Language Theory (DLT)","author":"J. Brzozowski","year":"2011","unstructured":"Brzozowski, J., Ye, Y.: Syntactic complexity of ideal and closed languages. In: Mauri, G., Leporati, A. (eds.) Proceedings of the 15th International Conference on Developments in Language Theory (DLT). LNCS. Springer, Heidelberg (to appear, 2011), Full paper at \n                    \n                      http:\/\/arxiv.org\/abs\/arXiv:1010.3263"},{"key":"8_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-281-4","volume-title":"Classical Finite Transformation Semigroups: An Introduction","author":"O. Ganyushkin","year":"2009","unstructured":"Ganyushkin, O., Mazorchuk, V.: Classical Finite Transformation Semigroups: An Introduction. Springer, Heidelberg (2009)"},{"key":"8_CR6","unstructured":"GAP-Group: GAP - Groups, Algorithms, Programming - a System for Computational Discrete Algebra (2010), \n                    \n                      http:\/\/www.gap-system.org\/"},{"issue":"27-29","key":"8_CR7","doi-asserted-by":"publisher","first-page":"2537","DOI":"10.1016\/j.tcs.2008.12.054","volume":"410","author":"Y.S. Han","year":"2009","unstructured":"Han, Y.S., Salomaa, K.: State complexity of basic operations on suffix-free regular languages. Theoret. Comput. Sci.\u00a0410(27-29), 2537\u20132548 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR8","first-page":"99","volume-title":"Automata, Formal Languages, and Related Topics, Inst. of Informatics","author":"Y.S. Han","year":"2009","unstructured":"Han, Y.S., Salomaa, K., Wood, D.: Operational state complexity of prefix-free regular languages. In: \u00c9sik, Z., F\u00fcl\u00f6p, Z. (eds.) Automata, Formal Languages, and Related Topics, Inst. of Informatics, pp. 99\u2013115. University of Szeged, Hungary (2009)"},{"issue":"3","key":"8_CR9","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/j.tcs.2004.04.010","volume":"327","author":"M. Holzer","year":"2004","unstructured":"Holzer, M., K\u00f6nig, B.: On deterministic finite automata and syntactic monoid size. Theoret. Comput. Sci.\u00a0327(3), 319\u2013347 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/BF02124933","volume":"46","author":"M. Hoyer","year":"1895","unstructured":"Hoyer, M.: Verallgemeinerung zweier s\u00e4tze aus der theorie der substitutionengruppen. Math. Ann.\u00a046, 539\u2013544 (1895)","journal-title":"Math. Ann."},{"key":"8_CR11","unstructured":"Krawetz, B., Lawrence, J., Shallit, J.: State complexity and the monoid of transformations of a finite set (2003), \n                    \n                      http:\/\/arxiv.org\/abs\/math\/0306416v1"},{"key":"8_CR12","first-page":"1266","volume":"194","author":"A.N. Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk SSSR\u00a0194, 1266\u20131268 (1970) (Russian); English translation: Soviet Math. Dokl. 11, 1373\u20131375 (1970)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"8_CR13","unstructured":"Myhill, J.: Finite automata and representation of events. Wright Air Development Center Technical Report, 57\u2013624 (1957)"},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","volume":"9","author":"A. Nerode","year":"1958","unstructured":"Nerode, A.: Linear automaton transformations. Proc. Amer. Math. Soc.\u00a09, 541\u2013544 (1958)","journal-title":"Proc. Amer. Math. Soc."},{"key":"8_CR15","doi-asserted-by":"crossref","first-page":"298","DOI":"10.4064\/fm-24-1-298-301","volume":"24","author":"S. Piccard","year":"1935","unstructured":"Piccard, S.: Sur les fonctions d\u00e9finies dans les ensembles finis quelconques. Fundamenta Mathematicae\u00a024, 298\u2013301 (1935)","journal-title":"Fundamenta Mathematicae"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01199686","volume":"11","author":"S. Piccard","year":"1938","unstructured":"Piccard, S.: Sur les bases du groupe sym\u00e9trique et du groupe alternant. Commentarii Mathematici Helvetici\u00a011, 1\u20138 (1938)","journal-title":"Commentarii Mathematici Helvetici"},{"key":"8_CR17","series-title":"Word, Language, Grammar","volume-title":"Handbook of Formal Languages","author":"J.E. Pin","year":"1997","unstructured":"Pin, J.E.: Syntactic Semigroups. In: Handbook of Formal Languages. Word, Language, Grammar, vol.\u00a01, Springer-Verlag New York, Inc., New York (1997)"},{"key":"8_CR18","doi-asserted-by":"crossref","first-page":"209","DOI":"10.4064\/fm-24-1-209-212","volume":"24","author":"W. Sierpi\u0144ski","year":"1935","unstructured":"Sierpi\u0144ski, W.: Sur les suites infinies de fonctions d\u00e9finies dans les ensembles quelconques. Fund. Math.\u00a024, 209\u2013212 (1935)","journal-title":"Fund. Math."},{"key":"8_CR19","first-page":"221","volume":"6","author":"S. Yu","year":"2001","unstructured":"Yu, S.: State complexity of regular languages. J. Autom. Lang. Comb.\u00a06, 221\u2013234 (2001)","journal-title":"J. Autom. Lang. Comb."}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22600-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,30]],"date-time":"2019-03-30T08:52:35Z","timestamp":1553935955000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22600-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642225994","9783642226007"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22600-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}