{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:44Z","timestamp":1753889744912,"version":"3.41.2"},"reference-count":29,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2010,9,20]],"date-time":"2010-09-20T00:00:00Z","timestamp":1284940800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We study logics defined in terms of second-order monadic monoidal and groupoidal quantifiers. These are generalized quantifiers defined by monoid and groupoid word-problems, equivalently, by regular and context-free languages. We give a computational classification of the expressive power of these logics over strings with varying built-in predicates. In particular, we show that ATIME(n) can be logically characterized in terms of second-order monadic monoidal quantifiers.<\/jats:p>","DOI":"10.2168\/lmcs-6(3:25)2010","type":"journal-article","created":{"date-parts":[[2010,11,26]],"date-time":"2010-11-26T21:17:19Z","timestamp":1290806239000},"source":"Crossref","is-referenced-by-count":1,"title":["On Second-Order Monadic Monoidal and Groupoidal Quantifiers"],"prefix":"10.46298","volume":"Volume 6, Issue 3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0115-5154","authenticated-orcid":false,"given":"Juha","family":"Kontinen","sequence":"first","affiliation":[]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2010,9,20]]},"reference":[{"key":"10.2168\/LMCS-6(3:25)2010_all99","doi-asserted-by":"crossref","unstructured":"E. Allender. The permanent requires large uniform threshold circuits.Chicago Journal of Theoretical Computer Science, 1999.","DOI":"10.4086\/cjtcs.1999.007"},{"key":"10.2168\/LMCS-6(3:25)2010_algo94","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1137\/S0097539792233907","volume":"23","author":"E. Allender and V. Gore","year":"1994","journal-title":"SIAM Journal on Computing"},{"key":"10.2168\/LMCS-6(3:25)2010_bacostth92","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"D. A. M. Barrington, K. Compton, H. Stra","year":"1992","journal-title":"Journal of Computer and System Sciences"},{"key":"10.2168\/LMCS-6(3:25)2010_baimst90","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. A. M. Barrington, N. Immerman, and H.","year":"1990","journal-title":"Journal of Computer and System Sciences"},{"key":"10.2168\/LMCS-6(3:25)2010_belemc93","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0304-3975(93)90253-P","volume":"107","author":"F. B\u00e9dard, F. Lemieux, and P. McKenzie","year":"1993","journal-title":"Theoretical Computer Science"},{"key":"10.2168\/LMCS-6(3:25)2010_bocrsi92","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(92)90125-Y","volume":"104","author":"D. P. Bovet, P. Crescenzi, and R. Silves","year":"1992","journal-title":"Theoretical Computer Science"},{"key":"10.2168\/LMCS-6(3:25)2010_bue62","unstructured":"J. R. B\u00fcchi. On a decision method in restricted second-order arithmetic. InProceedings Logic, Methodology and Philosophy of Sciences 1960, Stanford, CA, 1962. Stanford University Press."},{"key":"10.2168\/LMCS-6(3:25)2010_buel58","first-page":"834","volume":"5","author":"J. R. B\u00fcchi and C. C. Elgot","year":"1958","journal-title":"Notices of the American Mathematical Society"},{"key":"10.2168\/LMCS-6(3:25)2010_buvo98","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1142\/S0129054198000180","volume":"9","author":"H.-J. Burtschick and H. Vollmer","year":"1998","journal-title":"International Journal of Foundations of Computer Science 9:277-294, 1998"},{"issue":"3","key":"10.2168\/LMCS-6(3:25)2010_DDLW","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1002\/malq.19980440306","volume":"44","author":"A. Dawar, K. Doets, S. Lindell, and S. W","year":"1998","journal-title":"MLQ Math. Log. Q."},{"key":"10.2168\/LMCS-6(3:25)2010_MR1908783","doi-asserted-by":"crossref","unstructured":"M. Galota and H. Vollmer. A generalization of the B\u00fcchi-Elgot-Trakhtenbrot theorem. InComputer science logic (Paris, 2001), volume 2142 ofLecture Notes in Comput. Sci., pages 355-368. Springer, Berlin, 2001.","DOI":"10.1007\/3-540-44802-0_25"},{"key":"10.2168\/LMCS-6(3:25)2010_gre73","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S. Greibach","year":"1973","journal-title":"SIAM Journal on Computing"},{"key":"10.2168\/LMCS-6(3:25)2010_helascvowa93","doi-asserted-by":"crossref","unstructured":"U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, and K. W. Wagner. On the power of polynomial time bit-reductions. InProceedings 8th Structure in Complexity Theory, pages 200-207, 1993.","DOI":"10.1109\/SCT.1993.336526"},{"key":"10.2168\/LMCS-6(3:25)2010_imm99","doi-asserted-by":"crossref","unstructured":"N. Immerman.Descriptive Complexity. Graduate Texts in Computer Science. Springer Verlag, New York, 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"10.2168\/LMCS-6(3:25)2010_Kon3","unstructured":"J. Kontinen and H. Niemist\u00f6. Extensions of MSO and the monadic counting hierarchy.Information and Computation (to appear). Manuscript available at http:\/\/www.helsinki.fi\/ jkontine\/."},{"issue":"4","key":"10.2168\/LMCS-6(3:25)2010_lamcscvo01","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1006\/jcss.2000.1742","volume":"62","author":"C. Lautemann, P. McKenzie, T. Schwentick","year":"2001","journal-title":"Journal of Computer and Systems Sciences"},{"key":"10.2168\/LMCS-6(3:25)2010_lin66","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","volume":"32","author":"P. Lindstr\u00f6m","year":"1966","journal-title":"Theoria"},{"key":"10.2168\/LMCS-6(3:25)2010_loh08","unstructured":"M. Lohrey. Leaf languages and string compression. In R. Hariharan, M. Mukund, and V. Vinay, editors,FSTTCS 2008, volume 08004 ofDagstuhl Seminar Proceedings. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2008."},{"key":"10.2168\/LMCS-6(3:25)2010_mcpa71","unstructured":"R. McNaughton and S. Papert.Counter-Free Automata. MIT Press, 1971."},{"issue":"3","key":"10.2168\/LMCS-6(3:25)2010_MR1465635","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1002\/malq.19970430315","volume":"43","author":"M. More and F. Olive","year":"1997","journal-title":"Mathematical Logic Quarterly"},{"key":"10.2168\/LMCS-6(3:25)2010_pasc88","first-page":"287","volume":"36","author":"I. Parberry and G. Schnitger","year":"1988","journal-title":"Journal of Computer and System Sciences"},{"key":"10.2168\/LMCS-6(3:25)2010_pevo01","first-page":"179","volume":"4","author":"T. Peichl and H. Vollmer","year":"2001","journal-title":"Discrete Mathematics and Theoretical Computer Science 4:179-192, 2001"},{"key":"10.2168\/LMCS-6(3:25)2010_ruz80","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W. L. Ruzzo","year":"1980","journal-title":"Journal of Computer and System Sciences"},{"key":"10.2168\/LMCS-6(3:25)2010_str94","doi-asserted-by":"crossref","unstructured":"H. Straubing.Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston, 1994.","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"10.2168\/LMCS-6(3:25)2010_stthth95","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1006\/inco.1995.1067","volume":"118","author":"H. Straubing, D. Th\u00e9rien, and W. Thomas","year":"1995","journal-title":"Information and Computation"},{"key":"10.2168\/LMCS-6(3:25)2010_tra61","first-page":"326","volume":"140","author":"B. A. Trakhtenbrot","year":"1961","journal-title":"Doklady Akademii Nauk SSSR \\newblock In Russian"},{"key":"10.2168\/LMCS-6(3:25)2010_ven91","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/0022-0000(91)90020-6","volume":"43","author":"H. Venkateswaran","year":"1991","journal-title":"Journal of Computer and System Sciences"},{"key":"10.2168\/LMCS-6(3:25)2010_ver93a","first-page":"51","volume":"57","author":"N. K. Vereshchagin","year":"1993","journal-title":"Izvestija Rossijskoj Akademii Nauk \\newblock In Russian"},{"key":"10.2168\/LMCS-6(3:25)2010_vol99","doi-asserted-by":"crossref","unstructured":"H. Vollmer.Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoretical Computer Science. Springer Verlag, Berlin Heidelberg, 1999.","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1006\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1006\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T14:33:21Z","timestamp":1711982001000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,20]]},"references-count":29,"URL":"https:\/\/doi.org\/10.2168\/lmcs-6(3:25)2010","relation":{"is-same-as":[{"id-type":"arxiv","id":"1009.2893","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1009.2893","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2010,9,20]]},"article-number":"1006"}}