{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:33:48Z","timestamp":1725514428405},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_2","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"13-33","source":"Crossref","is-referenced-by-count":3,"title":["Generalizations of the Compactness Theorem and G\u00f6del\u2019s Completeness Theorem for Nonstandard Finite Structures"],"prefix":"10.1007","author":[{"given":"Mikl\u00f3s","family":"Ajtai","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M.: \n                    \n                      \n                    \n                    $\\Sigma_1^1$\n                  -formulae on finite structures. Annals of Pure and Applied Logic\u00a024, 1\u201348 (1983)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"4","key":"2_CR2","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/BF01302964","volume":"14","author":"M. Ajtai","year":"1994","unstructured":"Ajtai, M.: The Complexity of the Pigeonhole Principle. Combinatorica\u00a014(4), 417\u2013433 (1994)","journal-title":"Combinatorica"},{"key":"2_CR3","first-page":"200","volume-title":"Proc. ACM Symp. on Theory of Computing","author":"P. Beame","year":"1992","unstructured":"Beame, P., et al.: Exponential Lower Bound for the Pigeonhole Principle (extended abstract). In: Proc. ACM Symp. on Theory of Computing, pp. 200\u2013220. ACM Press, New York (1992)"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"Furst, M., Saxe, J.B., Sipser, M.: Parity, Circuits and the Polynomial Time Hierarchy. Mathematical Systems Theory\u00a017, 13\u201317 (1984)","journal-title":"Mathematical Systems Theory"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/BF01201353","volume":"39","author":"G. Gentzen","year":"1934","unstructured":"Gentzen, G.: Unterschungen \u00fcber das logische Schliessen. Mathematische Zeitschrift\u00a039, 176\u2013210, 405\u2013431 (1934)","journal-title":"Mathematische Zeitschrift"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Hastad, J.: Almost optimal lower bounds for small depth circuits. In: Proc. 18th Annu. ACM Symp. Theory Computing, pp. 6\u201320 (1986)","DOI":"10.1145\/12130.12132"},{"key":"2_CR7","volume-title":"Axiomatic Set Theory","author":"T. Jech","year":"1978","unstructured":"Jech, T.: Axiomatic Set Theory. Academic Press, San Diego (1978)"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/11780342_29","volume-title":"Logical Approaches to Computational Barriers","author":"J. Krajicek","year":"2006","unstructured":"Krajicek, J.: Forcing with random variables and proof complexity. In: Beckmann, A., et al. (eds.) CiE 2006. LNCS, vol.\u00a03988, pp. 277\u2013278. Springer, Heidelberg (2006)"},{"issue":"1","key":"2_CR9","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1145\/78935.78941","volume":"37","author":"A. M\u00e1t\u00e9","year":"1990","unstructured":"M\u00e1t\u00e9, A.: Nondeterministic polynomial-time computation and models of Arithmetic. Journal of the ACM\u00a037(1), 175\u2013193 (1990)","journal-title":"Journal of the ACM"},{"key":"2_CR10","series-title":"Studies in Logic and the Foundations of Mathematics","volume-title":"Proof Theory","author":"G. Takeuti","year":"1987","unstructured":"Takeuti, G.: Proof Theory, 2nd edn. Studies in Logic and the Foundations of Mathematics, vol.\u00a081. North-Holland, Amsterdam (1987)","edition":"2"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Yao, A.: Separating the polynomial time hierarchy by oracles. In: Proc. 26th Annu. IEEE Symp. Found. Comp. Sci., pp. 1\u201310 (1985)","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T09:38:06Z","timestamp":1619516286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_2","relation":{},"subject":[]}}