{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:45:59Z","timestamp":1725860759390},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319409450"},{"type":"electronic","value":"9783319409467"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-40946-7_8","type":"book-chapter","created":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T07:52:20Z","timestamp":1467705140000},"page":"89-100","source":"Crossref","is-referenced-by-count":3,"title":["Problems on Finite Automata and the Exponential Time Hypothesis"],"prefix":"10.1007","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Krebs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,6]]},"reference":[{"issue":"3","key":"8_CR1","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1145\/146637.146661","volume":"39","author":"M Beaudry","year":"1992","unstructured":"Beaudry, M., McKenzie, P., Th\u00e9rien, D.: The membership problem in aperiodic transformation monoids. J. ACM 39(3), 599\u2013616 (1992)","journal-title":"J. ACM"},{"issue":"1","key":"8_CR2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0304-3975(91)90075-D","volume":"88","author":"S Cho","year":"1991","unstructured":"Cho, S., Huynh, D.T.: Finite-automaton aperiodicity is PSPACE-complete. Theoret. Comput. Sci. 88(1), 99\u2013116 (1991)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"8_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(92)90002-W","volume":"97","author":"S Cho","year":"1992","unstructured":"Cho, S., Huynh, D.T.: The parallel complexity of finite-state automata problems. Inf. Comput. 97(1), 1\u201322 (1992)","journal-title":"Inf. Comput."},{"key":"8_CR4","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M Chrobak","year":"1986","unstructured":"Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci. 47, 149\u2013158 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015)"},{"key":"8_CR6","unstructured":"Dusart, P.: Estimates of some functions over primes without R.H. Technical report arXiv:1002.0442 [math.NT] (2010)"},{"issue":"4","key":"8_CR7","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1016\/j.jcss.2014.12.027","volume":"81","author":"H Fernau","year":"2015","unstructured":"Fernau, H., Heggernes, P., Villanger, Y.: A multi-parameter analysis of hard problems on deterministic finite automata. J. Comput. Syst. Sci. 81(4), 747\u2013765 (2015)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-319-26145-4_15","volume-title":"Combinatorial Image Analysis","author":"H Fernau","year":"2015","unstructured":"Fernau, H., Paramasivan, M., Schmid, M.L., Thomas, D.G.: Scanning pictures the boustrophedon way. In: Barneva, R.P., Bhattacharya, B.B., Brimkov, V.E. (eds.) IWCIA 2015. LNCS, vol. 9448, pp. 202\u2013216. Springer, Heidelberg (2015). doi: 10.1007\/978-3-319-26145-4_15"},{"key":"8_CR9","unstructured":"Fernau, H., Paramasivan, M., Schmid, M.L., Vorel, V.: Characterization, complexity results on jumping finite automata. Technical report arXiv:1512.00482 [cs.FL] (2015)"},{"key":"8_CR10","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF00263744","volume":"6","author":"Z Galil","year":"1976","unstructured":"Galil, Z.: Hierarchies of complete problems. Acta Informatica 6, 77\u201388 (1976)","journal-title":"Acta Informatica"},{"key":"8_CR11","unstructured":"Haase, C., Hofman, P.: Tightening the complexity of equivalence problems for commutative grammars. Technical report arXiv:1506.07774 [cs.FL] (2015)"},{"issue":"3","key":"8_CR12","doi-asserted-by":"crossref","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 - a survey. Inf. Comput. 209(3), 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"issue":"4","key":"8_CR13","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR14","unstructured":"Kopczy\u0144ski, E.: Complexity of problems of commutative grammars. Logical Methods Comput. Sci. 11(1:9) (2015). http:\/\/www.lmcs-online.org\/ojs\/viewarticle.php?id=1533"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: 18th Annual Symposium on Foundations of Computer Science, FOCS, pp. 254\u2013266. IEEE (1977)","DOI":"10.1109\/SFCS.1977.16"},{"key":"8_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1007\/3-540-55808-X_33","volume-title":"Mathematical Foundations of Computer Science 1992","author":"K-J Lange","year":"1992","unstructured":"Lange, K.-J., Rossmanith, P.: The emptiness problem for intersections of reg-ular languages. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol. 629, pp. 346\u2013354. Springer, Heidelberg (1992)"},{"key":"8_CR17","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the Exponential Time Hypothesis. EATCS Bull. 105, 41\u201372 (2011)","journal-title":"EATCS Bull."},{"issue":"7","key":"8_CR18","doi-asserted-by":"crossref","first-page":"1555","DOI":"10.1142\/S0129054112500244","volume":"23","author":"A Meduna","year":"2012","unstructured":"Meduna, A., Zemek, P.: Jumping finite automata. Int. J. Found. Comput. Sci. 23(7), 1555\u20131578 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3","key":"8_CR19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(83)90067-4","volume":"16","author":"IK Rystsov","year":"1983","unstructured":"Rystsov, I.K.: Polynomial complete problems in automata theory. Inf. Process. Lett. 16(3), 147\u2013151 (1983)","journal-title":"Inf. Process. Lett."},{"key":"8_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/11498490_2","volume-title":"Model-Based Testing of Reactive Systems","author":"S Sandberg","year":"2005","unstructured":"Sandberg, S.: 1 Homing and synchronizing sequences. In: Broy, M., Jonsson, B., Katoen, J.-P., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive Systems. LNCS, vol. 3472, pp. 5\u201333. Springer, Heidelberg (2005)"},{"key":"8_CR21","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"MP Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.P.: On finite monoids having only trivial subgroups. Inf. Control 8, 190\u2013194 (1965). (now Information and Computation)","journal-title":"Inf. Control"},{"issue":"3","key":"8_CR22","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/S0019-9958(85)80058-9","volume":"66","author":"J Stern","year":"1985","unstructured":"Stern, J.: Complexity of some problems from the theory of automata. Inf. Control 66(3), 163\u2013176 (1985). (now Information and Computation)","journal-title":"Inf. Control"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: preliminary report. In: Proceedings of the 5th Annual ACM Symposium on Theory of Computing, STOC, pp. 1\u20139. ACM (1973)","DOI":"10.1145\/800125.804029"},{"key":"8_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/3-540-44674-5_26","volume-title":"Implementation and Application of Automata","author":"HT Wareham","year":"2001","unstructured":"Wareham, H.T.: The parameterized complexity of intersection and composition operations on sets of finite-state automata. In: Yu, S., P\u0103un, A. (eds.) CIAA 2000. LNCS, vol. 2088, pp. 302\u2013310. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40946-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T13:50:47Z","timestamp":1498312247000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40946-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319409450","9783319409467"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40946-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}