{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:03:13Z","timestamp":1743037393173,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030887001"},{"type":"electronic","value":"9783030887018"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-88701-8_15","type":"book-chapter","created":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T23:06:25Z","timestamp":1634857585000},"page":"241-257","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deciding FO-definability of Regular Languages"],"prefix":"10.1007","author":[{"given":"Agi","family":"Kurucz","sequence":"first","affiliation":[]},{"given":"Vladislav","family":"Ryzhikov","sequence":"additional","affiliation":[]},{"given":"Yury","family":"Savateev","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Zakharyaschev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,22]]},"reference":[{"key":"15_CR1","unstructured":"Artale, A., et al.: Ontology-mediated query answering over temporal data: a survey. In: Schewe, S., Schneider, T., Wijsen, J. (eds.) TIME, vol. 90, pp. 1\u201337 (2017)"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"103536","DOI":"10.1016\/j.artint.2021.103536","volume":"299","author":"A Artale","year":"2021","unstructured":"Artale, A., et al.: First-order rewritability of ontology-mediated queries in linear temporal logic. Artif. Intell. 299, 103536 (2021)","journal-title":"Artif. Intell."},{"issue":"1","key":"15_CR3","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D Barrington","year":"1989","unstructured":"Barrington, D.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC$${^1}$$. J. Comput. Syst. Sci. 38(1), 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"15_CR4","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"D Barrington","year":"1992","unstructured":"Barrington, D., Compton, K., Straubing, H., Th\u00e9rien, D.: Regular languages in NC$${^1}$$. J. Comput. Syst. Sci. 44(3), 478\u2013499 (1992)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"15_CR5","doi-asserted-by":"publisher","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\u20134","key":"15_CR6","first-page":"427","volume":"62","author":"M Bennett","year":"2018","unstructured":"Bennett, M., Martin, G., O\u2019Bryant, K., Rechnitzer, A.: Explicit bounds for primes in arithmetic progressions. Illinois J. of Math. 62(1\u20134), 427\u2013532 (2018)","journal-title":"Illinois J. of Math."},{"issue":"1","key":"15_CR7","first-page":"1","volume":"13","author":"L Bern\u00e1tsky","year":"1997","unstructured":"Bern\u00e1tsky, L.: Regular expression star-freeness is PSPACE-complete. Acta Cybern. 13(1), 1\u201321 (1997)","journal-title":"Acta Cybern."},{"issue":"1\u20136","key":"15_CR8","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"JR B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundlagen der Math. 6(1\u20136), 66\u201392 (1960)","journal-title":"Z. Math. Logik und Grundlagen der Math."},{"key":"15_CR9","unstructured":"Carton, O., Dartois, L.: Aperiodic two-way transducers and fo-transductions. In: Kreutzer, S. (ed.) CSL 2015, vol. 41 pp. 160\u2013174 (2015)"},{"issue":"1","key":"15_CR10","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.: Finite-automaton aperiodicity is PSPACE-complete. Theor. Comp. Sci. 88(1), 99\u2013116 (1991)","journal-title":"Theor. Comp. Sci."},{"issue":"1\/2","key":"15_CR11","first-page":"240","volume":"87","author":"K Compton","year":"1990","unstructured":"Compton, K., Laflamme, C.: An algebra and a logic for NC$${^1}$$. Inf. Comput. 87(1\/2), 240\u2013262 (1990)","journal-title":"Inf. Comput."},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","volume":"98","author":"C Elgot","year":"1961","unstructured":"Elgot, C.: Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc. 98, 21\u201351 (1961)","journal-title":"Trans. Am. Math. Soc."},{"key":"15_CR13","unstructured":"Fleischer, L., Kufleitner, M.: The intersection problem for finite monoids. In: Niedermeier, R., Vall\u00e9e, B. (eds.) STACS 2018, vol. 96, pp. 1\u201314 (2018)"},{"key":"15_CR14","first-page":"139","volume":"38","author":"M Holzer","year":"2004","unstructured":"Holzer, M., K\u00f6nig, B.: Regular languages, sizes of syntactic monoids, graph colouring, state complexity results, and how these topics are related to each other. Bull. EATCS 38, 139\u2013155 (2004)","journal-title":"Bull. EATCS"},{"key":"15_CR15","doi-asserted-by":"publisher","unstructured":"Jukna, S.: Boolean Function Complexity. Advances and Frontiers, vol. 27. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-24508-4","DOI":"10.1007\/978-3-642-24508-4"},{"issue":"2","key":"15_CR16","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1017\/S0004972710000079","volume":"82","author":"G Kaplan","year":"2010","unstructured":"Kaplan, G., Levy, D.: Solvability of finite groups via conditions on products of 2-elements and odd p-elements. Bull. Austr. Math. Soc. 82(2), 265\u2013273 (2010)","journal-title":"Bull. Austr. Math. Soc."},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"King, O.: The subgroup structure of finite classical groups in terms of geometric configurations. In: Webb, B. (ed.) Surveys in Combinatorics, Society Lecture Note Series, vol. 327, pp. 29\u201356. Cambridge University Press (2005)","DOI":"10.1017\/CBO9780511734885.003"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of FOCS 1977, pp. 254\u2013266. IEEE Computer Society Press (1977)","DOI":"10.1109\/SFCS.1977.16"},{"key":"15_CR19","volume-title":"Counter-free automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-free automata. The MIT Press, Cambridge (1971)"},{"key":"15_CR20","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/978-3-540-77688-8_5","volume":"10","author":"A Poggi","year":"2008","unstructured":"Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. Data Seman. 10, 133\u2013173 (2008)","journal-title":"J. Data Seman."},{"key":"15_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4176-8","volume-title":"An introduction to the theory of groups","author":"J Rotman","year":"1999","unstructured":"Rotman, J.: An introduction to the theory of groups. Springer-Verlag, New York (1999). https:\/\/doi.org\/10.1007\/978-1-4612-4176-8"},{"key":"15_CR22","unstructured":"Ryzhikov, V., Savateev, Y., Zakharyaschev, M.: Deciding FO-rewritability of ontology-mediated queries in linear temporal logic. In: Combi, C., Eder, J., Reynolds, M. (eds.) TIME 2021, LIPIcs, pp. 6:1\u20137:15 (2021)"},{"issue":"2","key":"15_CR23","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"M Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.: On finite monoids having only trivial subgroups. Inf. Control 8(2), 190\u2013194 (1965)","journal-title":"Inf. Control"},{"issue":"2","key":"15_CR24","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"JC Shepherdson","year":"1959","unstructured":"Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3(2), 198\u2013200 (1959)","journal-title":"IBM J. Res. Dev."},{"issue":"3","key":"15_CR25","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)","journal-title":"Inf. Control"},{"key":"15_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite Automata, Formal Logic, and Circuit Complexity","author":"H Straubing","year":"1994","unstructured":"Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser Verlag, Basel (1994)"},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"Thompson, J.: Nonsolvable finite groups all of whose local subgroups are solvable. Bull. Amer. Math. Soc. 74(3), 383\u2013437 (1968)","DOI":"10.1090\/S0002-9904-1968-11953-6"},{"key":"15_CR28","first-page":"103","volume":"3","author":"B Trakhtenbrot","year":"1962","unstructured":"Trakhtenbrot, B.: Finite automata and the logic of one-place predicates. Siberian Math. J. 3, 103\u2013131 (1962)","journal-title":"Siberian Math. J."},{"issue":"5","key":"15_CR29","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0020-0190(89)90205-6","volume":"30","author":"M Vardi","year":"1989","unstructured":"Vardi, M.: A note on the reduction of two-way automata to one-way atuomata. Inf. Process. Lett. 30(5), 261\u2013264 (1989)","journal-title":"Inf. Process. Lett."},{"key":"15_CR30","unstructured":"Xiao, G., et al.: Ontology-based data access: a survey. In: Lang, J. (ed.) Proceedings of IJCAI 2018, pp. 5511\u20135519 (2018). ijcai.org"}],"container-title":["Lecture Notes in Computer Science","Relational and Algebraic Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-88701-8_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T05:55:23Z","timestamp":1673589323000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-88701-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030887001","9783030887018"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-88701-8_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"22 October 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RAMiCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Relational and Algebraic Methods in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Marseille","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 November 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 November 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ramics2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ramics19.lis-lab.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}