{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:50:39Z","timestamp":1742964639685,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031711114"},{"type":"electronic","value":"9783031711121"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-71112-1_13","type":"book-chapter","created":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T02:02:14Z","timestamp":1725328934000},"page":"180-194","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Decision Problems for\u00a0Subregular Classes"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1752-544X","authenticated-orcid":false,"given":"Michal","family":"Hospod\u00e1r","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4308-9159","authenticated-orcid":false,"given":"Viktor","family":"Olej\u00e1r","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-6501-1096","authenticated-orcid":false,"given":"Juraj","family":"\u0160ebej","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,3]]},"reference":[{"key":"13_CR1","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)"},{"issue":"3","key":"13_CR2","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1145\/321406.321409","volume":"14","author":"JA Brzozowski","year":"1967","unstructured":"Brzozowski, J.A.: Roots of star events. J. ACM 14(3), 466\u2013477 (1967). https:\/\/doi.org\/10.1145\/321406.321409","journal-title":"J. ACM"},{"issue":"3","key":"13_CR3","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/J.IC.2010.11.009","volume":"209","author":"JA Brzozowski","year":"2011","unstructured":"Brzozowski, J.A., Shallit, J.O., Xu, Z.: Decision problems for convex languages. Inf. Comput. 209(3), 353\u2013367 (2011). https:\/\/doi.org\/10.1016\/J.IC.2010.11.009","journal-title":"Inf. Comput."},{"issue":"1","key":"13_CR4","doi-asserted-by":"publisher","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. Theor. Comput. Sci. 88(1), 99\u2013116 (1991). https:\/\/doi.org\/10.1016\/0304-3975(91)90075-D","journal-title":"Theor. Comput. Sci."},{"issue":"05","key":"13_CR5","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1142\/S0129054111008647","volume":"22","author":"YS Han","year":"2011","unstructured":"Han, Y.S., Salomaa, K.: Overlap-free languages and solid codes. Int. J. Found. Comput. Sci. 22(05), 1197\u20131209 (2011). https:\/\/doi.org\/10.1142\/S0129054111008647","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"13_CR6","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1142\/S0129054106003887","volume":"17","author":"YS Han","year":"2006","unstructured":"Han, Y.S., Wang, Y., Wood, D.: Infix-free regular expressions and languages. Int. J. Found. Comput. Sci. 17(2), 379\u2013394 (2006). https:\/\/doi.org\/10.1142\/S0129054106003887","journal-title":"Int. J. Found. Comput. Sci."},{"key":"13_CR7","doi-asserted-by":"publisher","unstructured":"Hartmanis, J., Immerman, N., Mahaney, S.R.: One-way log-tape reductions. In: FoCS 1978, pp. 65\u201372. IEEE Computer Society (1978). https:\/\/doi.org\/10.1109\/SFCS.1978.31","DOI":"10.1109\/SFCS.1978.31"},{"issue":"3","key":"13_CR8","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 - a survey. Inf. Comput. 209(3), 456\u2013470 (2011). https:\/\/doi.org\/10.1016\/J.IC.2010.11.013","journal-title":"Inf. Comput."},{"key":"13_CR9","doi-asserted-by":"publisher","unstructured":"Holzer, M., Kutrib, M.: Structure and complexity of some subregular language families. In: The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski, pp. 59\u201382. World Scientific (2017). https:\/\/doi.org\/10.1142\/9789813148208_0003","DOI":"10.1142\/9789813148208_0003"},{"issue":"1","key":"13_CR10","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/0207007","volume":"7","author":"HB Hunt","year":"1978","unstructured":"Hunt, H.B., Rosenkrantz, D.J.: Computational parallels between the regular and context-free languages. SIAM J. Comput. 7(1), 99\u2013114 (1978). https:\/\/doi.org\/10.1137\/0207007","journal-title":"SIAM J. Comput."},{"key":"13_CR11","unstructured":"Iv\u00e1n, S., Nagy-Gy\u00f6rgy, J.: On the structure and syntactic complexity of generalized definite languages. CoRR abs\/1304.5714 (2013). http:\/\/arxiv.org\/abs\/1304.5714"},{"issue":"1","key":"13_CR12","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"ND Jones","year":"1975","unstructured":"Jones, N.D.: Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11(1), 68\u201385 (1975). https:\/\/doi.org\/10.1016\/S0022-0000(75)80050-X","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/J.TCS.2021.09.007","volume":"892","author":"H J\u00fcrgensen","year":"2021","unstructured":"J\u00fcrgensen, H., Staiger, L.: Automata for solid codes. Theor. Comput. Sci. 892, 25\u201347 (2021). https:\/\/doi.org\/10.1016\/J.TCS.2021.09.007","journal-title":"Theor. Comput. Sci."},{"key":"13_CR14","doi-asserted-by":"publisher","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: FoCS 1977, pp. 254\u2013266. IEEE Computer Society (1977). https:\/\/doi.org\/10.1109\/SFCS.1977.16","DOI":"10.1109\/SFCS.1977.16"},{"issue":"1","key":"13_CR15","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0208008","volume":"8","author":"J Opatrny","year":"1979","unstructured":"Opatrny, J.: Total ordering problem. SIAM J. Comput. 8(1), 111\u2013114 (1979). https:\/\/doi.org\/10.1137\/0208008","journal-title":"SIAM J. Comput."},{"key":"13_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5","volume-title":"Handbook of Formal Languages, Volume 1: Word, Language, Grammar","year":"1997","unstructured":"Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, Volume 1: Word, Language, Grammar. Springer, Cham (1997). https:\/\/doi.org\/10.1007\/978-3-642-59136-5"},{"issue":"2","key":"13_CR17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970). https:\/\/doi.org\/10.1016\/S0022-0000(70)80006-X","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"13_CR18","doi-asserted-by":"publisher","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(2), 190\u2013194 (1965). https:\/\/doi.org\/10.1016\/S0019-9958(65)90108-7","journal-title":"Inf. Control"},{"key":"13_CR19","first-page":"9","volume":"5","author":"HJ Shyr","year":"1974","unstructured":"Shyr, H.J., Thierrin, G.: Ordered automata and associated languages. Tamkang J. Math. 5, 9\u201320 (1974)","journal-title":"Tamkang J. Math."},{"issue":"1","key":"13_CR20","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/BF01761710","volume":"8","author":"HJ Shyr","year":"1974","unstructured":"Shyr, H.J., Thierrin, G.: Power-separating regular languages. Math. Syst. Theory 8(1), 90\u201395 (1974). https:\/\/doi.org\/10.1007\/BF01761710","journal-title":"Math. Syst. Theory"},{"key":"13_CR21","unstructured":"Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company (1997)"},{"issue":"3","key":"13_CR22","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/S0019-9958(85)80058-9","journal-title":"Inf. Control"},{"issue":"1","key":"13_CR23","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/S0022-0000(75)80014-6","volume":"10","author":"IH Sudborough","year":"1975","unstructured":"Sudborough, I.H.: On tape-bounded complexity classes and multihead finite automata. J. Comput. Syst. Sci. 10(1), 62\u201376 (1975). https:\/\/doi.org\/10.1016\/S0022-0000(75)80014-6","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"13_CR24","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The method of forced enumeration for nondeterministic automata. Acta Informatica 26(3), 279\u2013284 (1988). https:\/\/doi.org\/10.1007\/BF00299636","journal-title":"Acta Informatica"},{"issue":"1","key":"13_CR25","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF01691347","volume":"2","author":"G Thierrin","year":"1968","unstructured":"Thierrin, G.: Permutation automata. Math. Syst. Theory 2(1), 83\u201390 (1968). https:\/\/doi.org\/10.1007\/BF01691347","journal-title":"Math. Syst. Theory"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-71112-1_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T02:03:56Z","timestamp":1725329036000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-71112-1_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031711114","9783031711121"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-71112-1_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"3 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Akita","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}