{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T15:25:34Z","timestamp":1655997934995},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,2,27]],"date-time":"2008-02-27T00:00:00Z","timestamp":1204070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J of Log Lang and Inf"],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1007\/s10849-008-9058-5","type":"journal-article","created":{"date-parts":[[2008,2,26]],"date-time":"2008-02-26T04:37:10Z","timestamp":1204000630000},"page":"323-344","source":"Crossref","is-referenced-by-count":2,"title":["Partially Ordered Connectives and Monadic Monotone Strict NP"],"prefix":"10.1007","volume":"17","author":[{"given":"Lauri","family":"Hella","sequence":"first","affiliation":[]},{"given":"Merlijn","family":"Sevenster","sequence":"additional","affiliation":[]},{"given":"Tero","family":"Tulenheimo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,2,27]]},"reference":[{"key":"9058_CR1","doi-asserted-by":"crossref","unstructured":"Atserias, A. (2005). On digraph coloring problems and treewidth duality. In Proceedings of the 20th Annual Symposium on Logic in Computer Science (LICS 2005), pp. 106\u2013115.","DOI":"10.1109\/LICS.2005.31"},{"key":"9058_CR2","unstructured":"Atserias, A. (2006). On digraph coloring problems and treewidth duality. Retrieved April 1, 2007, from Albert Atserias\u2019 homepage, Universitat Polit\u00e8cnica de Catalunya: http:\/\/www.lsi.upc.es\/~atserias\/research.html ."},{"key":"9058_CR3","doi-asserted-by":"crossref","first-page":"409","DOI":"10.2307\/2270906","volume":"34","author":"J. Barwise","year":"1969","unstructured":"Barwise J. (1969). Applications of strict $$\\Pi^1_1$$ predicates to infinitary logic. Journal of Symbolic Logic 34: 409\u2013423","journal-title":"Journal of Symbolic Logic"},{"key":"9058_CR4","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF00258419","volume":"8","author":"J. Barwise","year":"1979","unstructured":"Barwise J. (1979). On branching quantifiers in English. Journal of Philosophical Logic 8: 47\u201380","journal-title":"Journal of Philosophical Logic"},{"key":"9058_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(86)90040-0","volume":"32","author":"A. Blass","year":"1986","unstructured":"Blass A., Gurevich Y. (1986). Henkin quantifiers and complete problems. Annals of Pure and Applied Logic 32: 1\u201316","journal-title":"Annals of Pure and Applied Logic"},{"key":"9058_CR6","doi-asserted-by":"crossref","unstructured":"Bulatov, A. (2002). A dichotomy theorem for constraints on a three-element set. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), pp. 649\u2013658.","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"9058_CR7","doi-asserted-by":"crossref","unstructured":"Dawar, A., & Gr\u00e4del, E. (1995). Generalized quantifiers and 0\u20131 laws. In Proceedings of the 10th Annual Symposium on Logic in Computer Science (LICS 1995), pp. 54\u201364.","DOI":"10.1109\/LICS.1995.523244"},{"key":"9058_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-28788-4","volume-title":"Finite model theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus H.-D., Flum J. (1999). Finite model theory. Springer, Berlin"},{"key":"9058_CR9","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/malq.19700160802","volume":"16","author":"H.B. Enderton","year":"1970","unstructured":"Enderton H.B. (1970). Finite partially-ordered quantifiers. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 16: 393\u2013397","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"9058_CR10","unstructured":"Fagin, R. (1974). Generalized first-order spectra and polynomial-time recognizable sets. In R. Karp (Ed.), Complexity of Computation, SIAM-AMS Proceedings (Vol. 7, pp. 43\u201373)."},{"key":"9058_CR11","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"Fagin R. (1975). Monadic generalized spectra. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 21: 89\u201396","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"9058_CR12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder T., Vardi M. (1998). The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing 28: 57\u2013104","journal-title":"SIAM Journal on Computing"},{"key":"9058_CR13","doi-asserted-by":"crossref","first-page":"545","DOI":"10.2307\/2275546","volume":"62","author":"G. Gottlob","year":"1997","unstructured":"Gottlob G. (1997). Relativized logspace and generalized quantifiers over finite ordered structures. Journal of Symbolic Logic 62: 545\u2013574","journal-title":"Journal of Symbolic Logic"},{"key":"9058_CR14","unstructured":"Gottlob, G., Leone, N., & Veith, H. (1995). Second order logic and the weak exponential hierarchies. In J. Wiedermann & P. H\u00e1jek (Eds.), Proceedings of the 20th International Symposium on Mathematical Foundations of Computer Science (MFCS 1995), Lecture Notes In Computer Science, (Vol. 969, pp. 66\u201381). London: Springer."},{"key":"9058_CR15","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell P., Ne\u0161et\u0159il J. (1990). On the complexity of H-coloring. Journal of Combinatorial Theory, Series B 48: 92\u2013110","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"9058_CR16","doi-asserted-by":"crossref","unstructured":"Hella, L., & Sandu, G. (1995). Partially ordered connectives and finite graphs. In M. Krynicki, M. Mostowski, & L. Szczerba (Eds.), Quantifiers: Logics, models and computation, (Vol. 2, pp. 79\u201388). Dordrecht: Kluwer.","DOI":"10.1007\/978-94-017-0524-0_4"},{"key":"9058_CR17","doi-asserted-by":"crossref","unstructured":"Hintikka, J. (1973). Quantifiers vs. quantification theory. Dialectica, 27, 329\u2013358. Reprinted in Linguistic Inquiry, 5, 153\u201377, 1974.","DOI":"10.1111\/j.1746-8361.1973.tb00624.x"},{"key":"9058_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman N. (1999). Descriptive complexity. Springer, New York"},{"key":"9058_CR19","doi-asserted-by":"crossref","unstructured":"Kolaitis, P., & Vardi, M. (1987). The decision problem for the probabilities of higher-order properties. In Proceedings of the nineteenth annual ACM conference on Theory of computing (STOC 1987), pp. 425\u2013435.","DOI":"10.1145\/28395.28441"},{"key":"9058_CR20","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1002\/malq.19930390134","volume":"39","author":"M. Krynicki","year":"1993","unstructured":"Krynicki M. (1993). Hierarchies of finite partially ordered connectives and quantifiers. Mathematical Logic Quarterly 39: 287\u2013294","journal-title":"Mathematical Logic Quarterly"},{"key":"9058_CR21","doi-asserted-by":"crossref","unstructured":"Krynicki, M., & Mostowski, M. (1995). Henkin quantifiers. In M. Krynicki, M. Mostowski, & L. Szczerba (Eds.), Quantifiers: Logics, models and computation, (Vol. 1, pp. 193\u2013262). Dordrecht: Kluwer.","DOI":"10.1007\/978-94-017-0522-6_7"},{"key":"9058_CR22","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1002\/malq.19930390134","volume":"39","author":"M. Krynicki","year":"1993","unstructured":"Krynicki M. (1993). Hierarchies of finite partially ordered connectives and quantifiers. Mathematical Logic Quarterly 39: 287\u2013294","journal-title":"Mathematical Logic Quarterly"},{"key":"9058_CR23","doi-asserted-by":"crossref","unstructured":"Krynicki, M., & Mostowski, M. (1995). Henkin quantifiers. In M. Krynicki, M. Mostowski, & L. Szczerba (Eds.), Quantifiers: Logics, models and computation, (Vol. 1, pp. 193\u2013262). Dordrecht: Kluwer.","DOI":"10.1007\/978-94-017-0522-6_7"},{"key":"9058_CR24","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0168-0072(89)90071-7","volume":"43","author":"M. Krynicki","year":"1989","unstructured":"Krynicki M., V\u00e4\u00e4n\u00e4nen J. (1989). Henkin and function quantifiers. Annals of Pure and Applied Logic 43: 273\u2013292","journal-title":"Annals of Pure and Applied Logic"},{"key":"9058_CR25","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner R.E. (1975). On the structure of polynomial time reducibility. Journal of the Association for Computing Machinery 22: 155\u2013171","journal-title":"Journal of the Association for Computing Machinery"},{"key":"9058_CR26","unstructured":"Mostowski, M. (1991). Arithmetic with the Henkin quantifier and its generalizations. In F. Gaillard & D. Richard (Eds.), S\u00e9minaire du Laboratoire Logique, Algorithmique et Informatique Clermontois, (Vol. II, pp. 1\u201325)."},{"key":"9058_CR27","volume-title":"Computational complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou C. (1994). Computational complexity. Addison-Wesley, Reading, MA"},{"key":"9058_CR28","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1002\/malq.19920380134","volume":"38","author":"G. Sandu","year":"1992","unstructured":"Sandu G., V\u00e4\u00e4n\u00e4nen J. (1992). Partially ordered connectives. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 38: 361\u2013372","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"9058_CR29","doi-asserted-by":"crossref","unstructured":"Schaefer, T. (1978). The complexity of satisfiability problems. In Proceedings of the 10th annual ACM symposium on Theory of computing (STOC 1978), pp. 216\u2013226.","DOI":"10.1145\/800133.804350"},{"key":"9058_CR30","unstructured":"Sevenster, M. (2006). Branches of imperfect information: Games, logic, and computation. Dissertation, ILLC, Universiteit van Amsterdam."},{"key":"9058_CR31","unstructured":"Sevenster, M., & Tulenheimo, T. (2006). Partially ordered connectives and $${\\Sigma}_1^1$$ on finite models. In A. Beckmann, U. Berger, B. L\u00f6we, & J. V. Tucker (Eds.), Logical Approaches to Computational Barriers. 2nd Conference on Computability in Europe (CiE 2006), Lecture Notes in Computer Science, (Vol. 3988, pp. 516\u2013525). Berlin: Springer."},{"key":"9058_CR32","doi-asserted-by":"crossref","first-page":"535","DOI":"10.2307\/2271440","volume":"35","author":"J. Walkoe W. Jr.","year":"1970","unstructured":"Walkoe W. J. Jr., (1970). Finite partially-ordered quantification. Journal of Symbolic Logic 35: 535\u2013555","journal-title":"Journal of Symbolic Logic"}],"container-title":["Journal of Logic, Language and Information"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10849-008-9058-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10849-008-9058-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10849-008-9058-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T22:31:01Z","timestamp":1559255461000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10849-008-9058-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2,27]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["9058"],"URL":"https:\/\/doi.org\/10.1007\/s10849-008-9058-5","relation":{},"ISSN":["0925-8531","1572-9583"],"issn-type":[{"value":"0925-8531","type":"print"},{"value":"1572-9583","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2,27]]}}}