{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T03:55:44Z","timestamp":1768017344076,"version":"3.49.0"},"reference-count":38,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2023,8,15]],"date-time":"2023-08-15T00:00:00Z","timestamp":1692057600000},"content-version":"unspecified","delay-in-days":75,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the classical theory of regular languages, the concept of recognition by profinite monoids is an important tool. Beyond regularity, Boolean spaces with internal monoids (BiMs) were recently proposed as a generalization. On the other hand, fragments of logic defining regular languages can be studied inductively via the so-called \u201cSubstitution Principle.\u201d In this paper, we make the logical underpinnings of this principle explicit and extend it to arbitrary languages using Stone duality. Subsequently, we show how it can be used to obtain topo-algebraic recognizers for classes of languages defined by a wide class of first-order logic fragments. This naturally leads to a notion of semidirect product of BiMs extending the classical such construction for profinite monoids. Our main result is a generalization of Almeida and Weil\u2019s Decomposition Theorem for semidirect products from the profinite setting to that of BiMs. This is a crucial step in a program to extend the profinite methods of regular language theory to the setting of complexity theory.<\/jats:p>","DOI":"10.1017\/s0960129523000294","type":"journal-article","created":{"date-parts":[[2023,8,15]],"date-time":"2023-08-15T08:30:53Z","timestamp":1692088253000},"page":"486-535","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["Substitution Principle and semidirect products"],"prefix":"10.1017","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0114-1572","authenticated-orcid":false,"given":"C\u00e9lia","family":"Borlido","sequence":"first","affiliation":[]},{"given":"Mai","family":"Gehrke","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,8,15]]},"reference":[{"key":"S0960129523000294_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/1-4020-3817-8_1"},{"key":"S0960129523000294_ref18","volume-title":"Graduate Texts in Computer Science","author":"Immerman","year":"1999"},{"key":"S0960129523000294_ref26","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2005014"},{"key":"S0960129523000294_ref36","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1145\/2559903","article-title":"Nonuniform ACC circuit lower bounds","volume":"61","author":"Williams","year":"2014","journal-title":"Journal of the ACM"},{"key":"S0960129523000294_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-88701-8_18"},{"key":"S0960129523000294_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14162-1_13"},{"key":"S0960129523000294_ref9","unstructured":"Eilenberg, S. (1976). Automata, Languages, and Machines. Vol. B, New York, Academic Press [Harcourt Brace Jovanovich Publishers]."},{"key":"S0960129523000294_ref5","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1964-001-5"},{"key":"S0960129523000294_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90014-A"},{"key":"S0960129523000294_ref21","unstructured":"Kuratowski, K. (1966). Topology. Vol. I, New York-London, Academic Press; Warsaw, Pa\u0144stwowe Wydawnictwo Naukowe. New edition, revised and augmented, Translated from the French by J. Jaworowski."},{"key":"S0960129523000294_ref34","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1016\/0022-0000(92)90029-I","article-title":"Closure of varieties of languages under products with counter","volume":"45","author":"Weil","year":"1992","journal-title":"Journal of Computer and System Sciences"},{"key":"S0960129523000294_ref35","unstructured":"Willard, S. (2004). General Topology, Mineola, NY, Dover Publications, Inc. Reprint of the 1970 original."},{"key":"S0960129523000294_ref7","unstructured":"Borlido, C. , Czarnetzki, S. , Gehrke, M. and Krebs, A. (2017). Stone duality and the substitution principle. In: Computer Science Logic 2017, LIPIcs, Leibniz International Proceedings in Informatics, vol. 82, Schloss Dagstuhl, Leibniz-Zent. Inform., Wadern, Art. No. 13, 20."},{"key":"S0960129523000294_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45995-2_46"},{"key":"S0960129523000294_ref3","first-page":"1","article-title":"Free profinite semigroups over semidirect products","volume":"39","author":"Almeida","year":"1995","journal-title":"Russian Mathematics (Iz. VUZ)"},{"key":"S0960129523000294_ref8","unstructured":"Dekkers, M. (2008). Stone Duality: An Application in the Theory of Formal Languages. Master\u2019s thesis, Radboud University Nijmegen, Netherlands."},{"key":"S0960129523000294_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45995-2_13"},{"key":"S0960129523000294_ref12","first-page":"246","volume-title":"ICALP 2008, Part II, Lecture Notes in Computer Science","author":"Gehrke","year":"2008"},{"key":"S0960129523000294_ref16","doi-asserted-by":"crossref","unstructured":"Gehrke, M. , Petri\u015fan, D. and Reggio, L. (2017). Quantifiers on languages and codensity monads. In: 2017 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS), NJ, IEEE, [Piscataway], 12.","DOI":"10.1109\/LICS.2017.8005140"},{"key":"S0960129523000294_ref20","doi-asserted-by":"crossref","unstructured":"Krebs, A. , Lange, K.-J. and Reifferscheid, S. (2005). Characterizing ${TC}^0$ in terms of infinite groups. In: STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24\u201326, 2005, Proceedings, 496\u2013507.","DOI":"10.1007\/978-3-540-31856-9_41"},{"key":"S0960129523000294_ref30","volume-title":"Progress in Theoretical Computer Science","author":"Straubing","year":"1994"},{"key":"S0960129523000294_ref28","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-3712-9","volume-title":"Extensions and Absolutes of Hausdorff Spaces","author":"Porter","year":"1988"},{"key":"S0960129523000294_ref33","first-page":"37","article-title":"Logic meets algebra: the case of regular languages","volume":"3","author":"Tesson","year":"2007","journal-title":"Logical Methods in Computer Science"},{"key":"S0960129523000294_ref24","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1951-0042109-4"},{"key":"S0960129523000294_ref25","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/978-3-642-59136-5_10","volume-title":"Handbook of Formal Languages","volume":"1","author":"Pin","year":"1997"},{"key":"S0960129523000294_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2015.12.007"},{"key":"S0960129523000294_ref14","unstructured":"Gehrke, M. , Jakl, T. and Reggio, L. (2020). A Cook\u2019s tour of duality in logic: from quantifiers, through Vietoris, to measures. arXiv:2007.15415, preprint."},{"key":"S0960129523000294_ref15","unstructured":"Gehrke, M. , Petri\u015fan, D. and Reggio, L. (2016). The Sch\u00fctzenberger product for syntactic spaces. In: 43rd International Colloquium on Automata, Languages, and Programming, LIPIcs. Leibniz International Proceedings in Informatics, vol. 55, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Art. No. 112, 14."},{"key":"S0960129523000294_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129521000074"},{"key":"S0960129523000294_ref37","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129523000294"},{"key":"S0960129523000294_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2019.05.002"},{"key":"S0960129523000294_ref1","doi-asserted-by":"crossref","unstructured":"Almeida, J. (1994). Finite Semigroups and Universal Algebra, World Scientific Publishing Co. Inc., River Edge, NJ. Translated from the 1992 Portuguese original and revised by the author.","DOI":"10.1142\/2481"},{"key":"#cr-split#-S0960129523000294_ref22.1","unstructured":"Lawvere, F. W. (2006). Adjointness in foundations. Repr. Theory and Applications of Categories"},{"key":"#cr-split#-S0960129523000294_ref22.2","unstructured":"(16) 1-16. Reprinted from Dialectica 23 (1969)."},{"key":"S0960129523000294_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679444"},{"key":"S0960129523000294_ref19","unstructured":"Johnstone, P. T. (1986). Stone Spaces, Cambridge Studies in Advanced Mathematics, vol. 3, Cambridge, Cambridge University Press. Reprint of the 1982 edition."},{"key":"S0960129523000294_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19550130302"},{"key":"S0960129523000294_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129523000294","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,18]],"date-time":"2023-09-18T02:32:31Z","timestamp":1695004351000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129523000294\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["S0960129523000294"],"URL":"https:\/\/doi.org\/10.1017\/s0960129523000294","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}