{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:25:33Z","timestamp":1740108333119,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T00:00:00Z","timestamp":1658707200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T00:00:00Z","timestamp":1658707200000},"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":["Acta Informatica"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s00236-022-00432-2","type":"journal-article","created":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T09:15:41Z","timestamp":1658740541000},"page":"321-336","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The regular languages of wire linear AC$$^0$$"],"prefix":"10.1007","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9828-9129","authenticated-orcid":false,"given":"Micha\u00ebl","family":"Cadilhac","sequence":"first","affiliation":[]},{"given":"Charles","family":"Paperman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,25]]},"reference":[{"issue":"02","key":"432_CR1","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1142\/S021819679600009X","volume":"06","author":"J Almeida","year":"1996","unstructured":"Almeida, J.: A syntactical proof of locality of DA. Int. J. Algebra Comput. 06(02), 165\u2013177 (1996). https:\/\/doi.org\/10.1142\/S021819679600009X","journal-title":"Int. J. Algebra Comput."},{"key":"432_CR2","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"DAM Barrington","year":"1992","unstructured":"Barrington, D.A.M., Compton, K., Straubing, H., Th\u00e9rien, D.: Regular languages in $${\\rm NC}^1$$. J. Comput. Syst. Sci. 44, 478\u2013499 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"432_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.jcss.2004.07.004","volume":"70","author":"DAM Barrington","year":"2005","unstructured":"Barrington, D.A.M., Immerman, N., Lautemann, C., Schweikardt, N., Th\u00e9rien, D.: First-order expressibility of languages with neutral letters or: the Crane Beach Conjecture. J. Comput. Syst. Sci. 70, 101\u2013127 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"432_CR4","doi-asserted-by":"crossref","unstructured":"Behle, C., Krebs, A., Lange, K.J., McKenzie, P.: In: Rovan, B., Sassone, V., Widmayer, P. (eds.) Mathematical Foundations of Computer Science 2012, pp. 590\u2013602. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32589-2_52"},{"key":"432_CR5","doi-asserted-by":"publisher","unstructured":"Behle, C., Lange, K.: In: 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16\u201320 July 2006, Prague, Czech Republic, pp. 183\u2013189. IEEE Computer Society (2006). https:\/\/doi.org\/10.1109\/CCC.2006.20","DOI":"10.1109\/CCC.2006.20"},{"issue":"1","key":"432_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0022-0000(78)90049-1","volume":"16","author":"J Brzozowski","year":"1978","unstructured":"Brzozowski, J., Knast, R.: The dot-depth hierarchy of star-free languages is infinite. J. Comput. Syst. Sci. 16(1), 37\u201355 (1978). https:\/\/doi.org\/10.1016\/0022-0000(78)90049-1","journal-title":"J. Comput. Syst. Sci."},{"key":"432_CR7","doi-asserted-by":"publisher","unstructured":"Chandra, A.K., Fortune, S., Lipton, R.: In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC \u201983, pp. 52\u201360. Association for Computing Machinery, New York (1983). https:\/\/doi.org\/10.1145\/800061.808732","DOI":"10.1145\/800061.808732"},{"key":"432_CR8","doi-asserted-by":"crossref","unstructured":"Dartois, L., Paperman, C.: In: Kosowski, A., Walukiewicz, I. (eds.) Fundamentals of Computation Theory, pp. 160\u2013172. Springer International Publishing, Cham (2015)","DOI":"10.1007\/978-3-319-22177-9_13"},{"issue":"3","key":"432_CR9","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1142\/S0129054108005802","volume":"19","author":"V Diekert","year":"2008","unstructured":"Diekert, V., Gastin, P., Kufleitner, M.: A survey on small fragments of first-order logic over finite words. Int. J. Found. Comput. Sci. 19(3), 513\u2013548 (2008). https:\/\/doi.org\/10.1142\/S0129054108005802","journal-title":"Int. J. Found. Comput. Sci."},{"key":"432_CR10","doi-asserted-by":"crossref","unstructured":"Hahn, M., Krebs, A., Lange, K.J., Ludwig, M.: In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) Mathematical Foundations of Computer Science 2015, pp. 384\u2013394. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-48054-0_32"},{"key":"432_CR11","doi-asserted-by":"publisher","unstructured":"Koucky, M., Poloczek, S., Lautemann, C., Therien, D.: In: 21st Annual IEEE Conference on Computational Complexity (CCC\u201906), pp. 12\u2013201. (2006). https:\/\/doi.org\/10.1109\/CCC.2006.12","DOI":"10.1109\/CCC.2006.12"},{"key":"432_CR12","doi-asserted-by":"publisher","unstructured":"Kouck\u00fd, M., Pudl\u00e1k, P., Th\u00e9rien, D.: In: STOC, pp. 257\u2013265. ACM (2005). https:\/\/doi.org\/10.1145\/1060590.1060629","DOI":"10.1145\/1060590.1060629"},{"key":"432_CR13","doi-asserted-by":"publisher","unstructured":"Krebs, A., Lange, K., Ludwig, M.: In: Mayr, E.W., Ollinger, N. (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, 4\u20137 March 2015, Garching, Germany, LIPIcs, vol.\u00a030, pp. 594\u2013607. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2015). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2015.594","DOI":"10.4230\/LIPIcs.STACS.2015.594"},{"key":"432_CR14","doi-asserted-by":"publisher","unstructured":"Krebs, A., Lange, K., Reifferscheid, S.: In: Diekert, V., Durand, B. (eds.) STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, 24\u201326 Feb 2005, Proceedings, Lecture Notes in Computer Science, vol. 3404, pp. 496\u2013507. Springer (2005). https:\/\/doi.org\/10.1007\/978-3-540-31856-9_41","DOI":"10.1007\/978-3-540-31856-9_41"},{"key":"432_CR15","doi-asserted-by":"publisher","unstructured":"Kufleitner, M., Lauser, A.: In: Portier, N., Wilke, T. (eds.) 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a020, pp. 305\u2013316. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2013). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2013.305","DOI":"10.4230\/LIPIcs.STACS.2013.305"},{"key":"432_CR16","doi-asserted-by":"publisher","unstructured":"Lange, K.: In: 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21\u201324 June 2004, Amherst, MA, USA, pp. 123\u2013129. IEEE Computer Society (2004). https:\/\/doi.org\/10.1109\/CCC.2004.1313817","DOI":"10.1109\/CCC.2004.1313817"},{"key":"432_CR17","unstructured":"Paperman, C.: Circuits bool\u00e9ens, pr\u00e9dicats modulaires et langages r\u00e9guliers. Ph.D. thesis, Universit\u00e9 Paris Diderot (2013)"},{"issue":"01","key":"432_CR18","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1051\/ita:2005014","volume":"39","author":"J\u00c9 Pin","year":"2005","unstructured":"Pin, J.\u00c9., Straubing, H.: Some results on C-varieties. RAIRO-Theor. Inform. Appl. 39(01), 239\u2013262 (2005)","journal-title":"RAIRO-Theor. Inform. Appl."},{"key":"432_CR19","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. Birkh\u00e4user, Boston (1994)"},{"key":"432_CR20","doi-asserted-by":"crossref","unstructured":"Tesson, P., Th\u00e9rien, D. In: Semigroups, pp. 475\u2013500. Automata and Languages (World Scientific, Algorithms (2002)","DOI":"10.1142\/9789812776884_0021"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00432-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-022-00432-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00432-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,29]],"date-time":"2024-09-29T20:23:36Z","timestamp":1727641416000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-022-00432-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,25]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["432"],"URL":"https:\/\/doi.org\/10.1007\/s00236-022-00432-2","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2022,7,25]]},"assertion":[{"value":"15 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}