{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T12:22:04Z","timestamp":1765887724080,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,6,25]],"date-time":"2015-06-25T00:00:00Z","timestamp":1435190400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J of Log Lang and Inf"],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s10849-015-9218-3","type":"journal-article","created":{"date-parts":[[2015,6,24]],"date-time":"2015-06-24T06:41:03Z","timestamp":1435128063000},"page":"289-305","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Dependence Logic with a Majority Quantifier"],"prefix":"10.1007","volume":"24","author":[{"given":"Arnaud","family":"Durand","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6556-178X","authenticated-orcid":false,"given":"Johannes","family":"Ebbing","sequence":"additional","affiliation":[]},{"given":"Juha","family":"Kontinen","sequence":"additional","affiliation":[]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,25]]},"reference":[{"issue":"2","key":"9218_CR1","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s11229-008-9415-6","volume":"167","author":"S Abramsky","year":"2009","unstructured":"Abramsky, S., & V\u00e4\u00e4n\u00e4nen, J. (2009). From IF to BI. Synthese, 167(2), 207\u2013230.","journal-title":"Synthese"},{"key":"9218_CR2","first-page":"19","volume":"7","author":"E Allender","year":"1999","unstructured":"Allender, E. (1999). The permanent requires large uniform threshold circuits. Chicago Journal of Theoretical Computer Science, 7, 19. (electronic).","journal-title":"Chicago Journal of Theoretical Computer Science"},{"issue":"1\u20133","key":"9218_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0168-0072(01)00082-3","volume":"115","author":"A Andersson","year":"2002","unstructured":"Andersson, A. (2002). On second-order generalized quantifiers and finite structures. Annals of Pure and Applied Logic, 115(1\u20133), 1\u201332.","journal-title":"Annals of Pure and Applied Logic"},{"issue":"3","key":"9218_CR4","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1142\/S0129054198000180","volume":"9","author":"H-J Burtschick","year":"1998","unstructured":"Burtschick, H.-J., & Vollmer, H. (1998). Lindstr\u00f6m quantifiers and leaf language definability. International Journal of Foundations of Computer Science, 9(3), 277\u2013294.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"9218_CR5","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"252","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)","author":"A Durand","year":"2011","unstructured":"Durand, A., Ebbing, J., Kontinen, J., & Vollmer, H. (2011). Dependence logic with a majority quantifier. In S. Chakraborty & A. Kumar (Eds.), IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) (Vol. 13, pp. 252\u2013263)., Leibniz International Proceedings in Informatics (LIPIcs) Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"9218_CR6","unstructured":"Ebbing, J. (2014). Complexity and expressivity of dependence logic extensions. PhD thesis, Leibniz Universit\u00e4t Hannover."},{"key":"9218_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-28788-4","volume-title":"Finite model theory perspectives in mathematical logic","author":"H-D Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., & Flum, J. (1999). Finite model theory perspectives in mathematical logic (2nd ed.). Heidelberg: Springer.","edition":"2"},{"issue":"3","key":"9218_CR8","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s10849-012-9162-4","volume":"21","author":"F Engstr\u00f6m","year":"2012","unstructured":"Engstr\u00f6m, F. (2012). Generalized quantifiers in dependence logic. Journal of Logic, Language and Information, 21(3), 299\u2013324.","journal-title":"Journal of Logic, Language and Information"},{"issue":"1","key":"9218_CR9","doi-asserted-by":"crossref","first-page":"307","DOI":"10.2178\/jsl.7801210","volume":"78","author":"F Engstr\u00f6m","year":"2013","unstructured":"Engstr\u00f6m, F., & Kontinen, J. (2013). Characterizing quantifier extensions of dependence logic. The Journal of Symbolic Logic, 78(1), 307\u2013316.","journal-title":"The Journal of Symbolic Logic"},{"issue":"1","key":"9218_CR10","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.apal.2011.08.005","volume":"163","author":"P Galliani","year":"2012","unstructured":"Galliani, P. (2012). Inclusion and exclusion dependencies in team semantics\u2014On some logics of imperfect information. Annals of Pure and Applied Logic, 163(1), 68\u201384.","journal-title":"Annals of Pure and Applied Logic"},{"issue":"2","key":"9218_CR11","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/s11225-013-9479-2","volume":"101","author":"E Gr\u00e4del","year":"2013","unstructured":"Gr\u00e4del, E., & V\u00e4\u00e4n\u00e4nen, J. A. (2013). Dependence and independence. Studia Logica, 101(2), 399\u2013410.","journal-title":"Studia Logica"},{"key":"9218_CR12","unstructured":"Henkin, L. (1961). Some remarks on infinitely long formulas. In Infinitistic Methods (Proceedings of the Symposium of Foundations of Mathematics, Warsaw, 1959) (pp. 167\u2013183). Pergamon, Oxford."},{"key":"9218_CR13","doi-asserted-by":"crossref","unstructured":"Hintikka, J., & Sandu, G. (1989). Informational independence as a semantical phenomenon. In Logic, methodology and philosophy of science, VIII (Moscow, 1987), Vol 126 of Studies in Logic and the Foundations of Mathematics (pp. 571\u2013589). North-Holland, Amsterdam.","DOI":"10.1016\/S0049-237X(08)70066-1"},{"issue":"1","key":"9218_CR14","doi-asserted-by":"crossref","first-page":"188","DOI":"10.2178\/jsl\/1140641168","volume":"71","author":"J Kontinen","year":"2006","unstructured":"Kontinen, J. (2006). The hierarchy theorem for second order generalized quantifiers. The Journal of Symbolic Logic, 71(1), 188\u2013202.","journal-title":"The Journal of Symbolic Logic"},{"issue":"1","key":"9218_CR15","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/1459010.1459017","volume":"10","author":"J Kontinen","year":"2009","unstructured":"Kontinen, J. (2009). A logical characterization of the counting hierarchy. ACM Transactions on Computational Logic (TOCL), 10(1), 7.","journal-title":"ACM Transactions on Computational Logic (TOCL)"},{"issue":"3","key":"9218_CR16","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/s00153-010-0177-8","volume":"49","author":"J Kontinen","year":"2010","unstructured":"Kontinen, J. (2010). Definability of second order generalized quantifiers. Archive for Mathematical Logic, 49(3), 379\u2013398.","journal-title":"Archive for Mathematical Logic"},{"issue":"1","key":"9218_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2010.09.002","volume":"209","author":"J Kontinen","year":"2011","unstructured":"Kontinen, J., & Niemist\u00f6, H. (2011). Extensions of MSO and the monadic counting hierarchy. Information and Computation, 209(1), 1\u201319.","journal-title":"Information and Computation"},{"issue":"6","key":"9218_CR18","doi-asserted-by":"crossref","first-page":"1152","DOI":"10.1016\/j.jcss.2014.04.007","volume":"80","author":"J Kontinen","year":"2014","unstructured":"Kontinen, J., & Szymanik, J. (2014). A characterization of definability of second-order generalized quantifiers with applications to non-definability. Journal of Computer and System Sciences, 80(6), 1152\u20131162.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"9218_CR19","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s10849-009-9082-0","volume":"18","author":"J Kontinen","year":"2009","unstructured":"Kontinen, J., & V\u00e4\u00e4n\u00e4nen, J. (2009). On definability in dependence logic. Journal of Logic, Language and Information, 18(3), 317\u2013332.","journal-title":"Journal of Logic, Language and Information"},{"key":"9218_CR20","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","volume":"32","author":"P Lindstr\u00f6m","year":"1966","unstructured":"Lindstr\u00f6m, P. (1966). First order predicate logic with generalized quantifiers. Theoria, 32, 186\u2013195.","journal-title":"Theoria"},{"issue":"2","key":"9218_CR21","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s11225-013-9483-6","volume":"101","author":"P Lohmann","year":"2013","unstructured":"Lohmann, P., & Vollmer, H. (2013). Complexity results for modal dependence logic. Studia Logica, 101(2), 343\u2013366.","journal-title":"Studia Logica"},{"issue":"6","key":"9218_CR22","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1093\/logcom\/exn102","volume":"19","author":"M Sevenster","year":"2009","unstructured":"Sevenster, M. (2009). Model-theoretic and computational properties of modal dependence logic. Journal of Logic and Computation, 19(6), 1157\u20131173.","journal-title":"Journal of Logic and Computation"},{"issue":"5","key":"9218_CR23","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S. (1991). PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5), 865\u2013877.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"9218_CR24","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"S Toda","year":"1992","unstructured":"Toda, S., & Watanabe, O. (1992). Polynomial time 1-turing reductions from #PH to #P. Theoretical Computer Science, 100(1), 205\u2013221.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"9218_CR25","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/116825.116858","volume":"38","author":"J Tor\u00e1n","year":"1991","unstructured":"Tor\u00e1n, J. (1991). Complexity classes defined by counting quantifiers. Journal of the ACM, 38(3), 753\u2013774.","journal-title":"Journal of the ACM"},{"key":"9218_CR26","doi-asserted-by":"crossref","unstructured":"V\u00e4\u00e4n\u00e4nen, J. (1999). Generalized quantifiers, an introduction. In Generalized quantifiers and computation (Aix-en-Provence, 1997), Vol 1754 of Lecture Notes in Computer Science (pp. 1\u201317). Berlin: Springer.","DOI":"10.1007\/3-540-46583-9"},{"key":"9218_CR27","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511611193","volume-title":"Dependence logic: A new approach to independence friendly logic, volume 70 of London mathematical society student texts","author":"J V\u00e4\u00e4n\u00e4nen","year":"2007","unstructured":"V\u00e4\u00e4n\u00e4nen, J. (2007). Dependence logic: A new approach to independence friendly logic, volume 70 of London mathematical society student texts. Cambridge: Cambridge University Press."},{"key":"9218_CR28","first-page":"237","volume-title":"New perspectives on games and interaction, volume 5 of texts in logic and games","author":"J V\u00e4\u00e4n\u00e4nen","year":"2008","unstructured":"V\u00e4\u00e4n\u00e4nen, J. (2008). Modal dependence logic. In K. Apt & R. van Rooij (Eds.), New perspectives on games and interaction, volume 5 of texts in logic and games (pp. 237\u2013254). Amsterdam: Amsterdam University Press."},{"key":"9218_CR29","doi-asserted-by":"crossref","unstructured":"Vollmer, H. (1999). Introduction to circuit complexity\u2014-A uniform approach. In W. Brauer, G. Rozenberg & A. Salomaa (Eds.), Texts in Theoretical Computer Science\u2014An EATCS Series. Berlin, Heidelberg: Springer.","DOI":"10.1007\/978-3-662-03927-4"},{"key":"9218_CR30","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K Wagner","year":"1986","unstructured":"Wagner, K. (1986). The complexity of combinatorial problems with succint input representation. Acta Informatica, 23, 325\u2013356.","journal-title":"Acta Informatica"},{"issue":"2","key":"9218_CR31","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/s11225-013-9476-5","volume":"101","author":"F Yang","year":"2013","unstructured":"Yang, F. (2013). Expressing second-order sentences in intuitionistic dependence logic. Studia Logica, 101(2), 323\u2013342.","journal-title":"Studia Logica"}],"container-title":["Journal of Logic, Language and Information"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10849-015-9218-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10849-015-9218-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10849-015-9218-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,9]],"date-time":"2024-06-09T17:44:43Z","timestamp":1717955083000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10849-015-9218-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,25]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["9218"],"URL":"https:\/\/doi.org\/10.1007\/s10849-015-9218-3","relation":{},"ISSN":["0925-8531","1572-9583"],"issn-type":[{"type":"print","value":"0925-8531"},{"type":"electronic","value":"1572-9583"}],"subject":[],"published":{"date-parts":[[2015,6,25]]}}}