Andrzej Grzegorczyk's Contribution to Computer Science

• Autorzy: Salwicki A.
• Języki publikacji: EN

Abstrakty

EN

The paper of Andrzej Grzegorczyk [19] on hierachy of the primitive recursive classes dates for 1953. This is the most frequently cited article of Polish author in computer science literature, having some hundreds citations. Moreover, many citations are in the papers of eminent computer scientists e.g. [10, 24, 33, 34, 31], sometimes the laureates of prestigious awards. In this paper we make an attempt to present Andrzej Grzegorczyk as a computer scientist.

Słowa kluczowe

EN

Grzegorczyk hierarchy

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 81, nr 1-3
• Strony: 315--323
• Opis fizyczny: bibliogr. 47 poz.

Twórcy

autor

Salwicki A.

• National Institute of Telecommunications, , 04-854 Warsaw, Poland,

Bibliografia

• [1] Axt, P.: Enumeration and the Grzegorczyk hierarchy, Z. Math. Logik Grundlagen Math, 9, 1963, 53-65.
• [2] Bellantoni, S. J., and and Niggl, K.H.: Ranking Primitive Recursions: the Low Grzegorczyk Classes Revisited, SIAM journal on computing, 29, 2000, 401-415.
• [3] Beltyukov, A.: A computer description and a hierarchy of initial Grzegorczyk classes, Journal of Soviet Mathematics, 20, 1982, 2280 - 2289, Translation from Zap. Nauk. Sem. Lening. Otd.Mat. Inst., V. A. Steklova AN SSSR, 88, 1979, 30 - 46 .
• [4] Bonner, A.J. and Mecca, G.: Querying sequence databases with transducers, Acta Informatica, 36, 2000, 511-544.
• [5] Bournez, O., Hainry, E.: An analog characterization of elementarily computable functions over the real numbers, in ICALP 2004 : international colloquium on automata, languages and programming (J. Diaz, J. Karhumaki, A. Lepistö, D. Sannella, Eds.), LNCS 3142, 2004, 116-127.
• [6] Brainerd,W., Landweber, L.: Theory of Computation, J. Wiley, New York, NY, USA, 1974.
• [7] Campagnolo, M., Moore, C., Costa, J.: An analog characterization of the Grzegorczyk hierarchy, Journal of Complexity, 18, 2002, 977-1000.
• [8] Cichon, E.A., Wainer, S.: The Slow-Growing and the Grzegorczyk Hierarchies, The Journal of Symbolic Logic, 48, 1983, 399-408.
• [9] Cohn, A. G., Bennett, B., Gooday, J., Gotts, N. M.: Qualitative Spatial Representation and Reasoning with the Region Connection Calculus, GeoInformatica, 1, 1997, 275-317.
• [10] Cook, S. A.: An overview of computational complexity, Commun. ACM, 26(6), 1983, 400-408.
• [11] Cornaros,C.: On Grzegorczyk Induction, Annals of Pure and Applied Logic, 74(1), 1995, 1-21.
• [12] Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity, Springer, Berlin, January 2008.
• [13] Gabbay, D.M.: On 2nd order intuitionistic propositional calculus with full comprehension, Annals of Mathematical Logic 16, 1974, 177-186.
• [14] Gabbay D.M.: Semantical Investigations in Heyting's Intuitionistic Logic, Synthese Library,148, D. Reidel, 1981, Dordrecht.
• [15] Gakwaya, J.-S.: Extended Grzegorczyk Hierarchy in the BSS Model of Computability, in: Foundations of Computational Mathematics (Cucker, Shub Eds.), Springer, Berlin, 1997, 127-151.
• [16] Görnemann, S.: A logic stronger than intuitionism, Journal of Symbolic Logic, 36(2), 1971, 249-261.
• [17] Grozea, C.: NP predicates computable in the weakest level of the Grzegorczyck hierarchy, Journal of Automata, Languages and Combinatorics, 9(2-3), September 2004, 269 - 279.
• [18] Grzegorczyk, A.: Undecidability of some topological theories, Fundamenta Mathematicae, 38, 1951, 137-152.
• [19] Grzegorczyk, A.: Some classes of recursive functions, Rozprawy Matematyczne, 4, 1953, 3-45. Take a free copy from: http://matwbn.icm.edu.pl/ksiazki/rm/rmo4/rm0401/pdf
• [20] Grzegorczyk, A.: On the definitions of computable real continuous functions, Fundamenta Mathematicae, XLIV, 1957, 61-71.
• [21] Grzegorczyk, A.: Recursive objects in all finite types, Fundamenta Mathematicae, LIV, 1964, 73-93.
• [22] Grzegorczyk, A.: A philosophically plausible formal iterpretation of intuitionistic logic, IndagationesMathematicae, 26, 1964, 596-601.
• [23] Grzegorczyk, A.: Undecidability without Arithmetization, Studia Logica, 79, 2, 2005, 163-230.
• [24] Hartmanis, J., Hopcroft, J. E.: An Overview of the Theory of Computational Complexity, J. ACM, 18, 3, 1971, 444-475.
• [25] Krajewski, S., Woleński, J.: Andrzej Grzegorczyk: Logic and Philosophy, Fundamenta Informaticae, 81(1-3), 2007, 1-17.
• [26] Kristiansen, L., Barra, M.: The Small Grzegorczyk Classes and the Typed lambda-Calculus, in CiE: New Computational Paradigms (S. B. Cooper, B. Löwe, L. Torenvliet, Eds.), Springer, 2005, 252-262.
• [27] Kutyłowski, M.: A generalized Grzegorczyk hierarchy and low complexity classes, Information and Computation, 72(2), 1987, 133-149.
• [28] Kutyłowski,M.: Small Grzegorczyk Classes, Journal of the London Mathematical Society, 2(2), 1987, 193.
• [29] Kutyłowski,M. and Lory´s, K.: A note about E0 = E2 ? Problem, Zt. math. Logik und Grundlag. Math., 33, 1987, 115-121.
• [30] Maksimova, L.: On modal Grzegorczyk logic, Fundamenta Informaticae, 81(1-3), 2007, 203-210.
• [31] Mehlhorn, K.: Polynomial and abstract subrecursive classes, Proceedings of the sixth annual ACM symposium on Theory of computing, Annual ACM Symposium on Theory of Computing, ACM Press, Seattle,WA, 1974, see also J. Comp.Syst Sci. 12, 1976, 147-178.
• [32] Meyer, A. R.: Depth of nesting and the Grzegorczyk hierarchy, Notices Amer.Math. Soc., 13, 1965, 622-656.
• [33] Meyer, A. R., Ritchie, D. M.: The complexity of loop programs, Proceedings of the 1967 22nd national ACM conference, ACM Press, New York, NY, USA, 1967, 465-469.
• [34] Muchnick, S.: The vectorized Grzegorczyk hierarchy, Z. Math. Logik Grundlag. Math,22, 1976, 441-480.
• [35] Mycka, J., Costa, J.: Undecidability over Continuous Time, Logic Journal of IGPL, 14, 5, 2006, 469.
• [36] Ornaghi, M., Benini, M., Ferrari, M., Fiorentini, C., Momigliano, A.: A Constructive Object Oriented Modeling Language for Information Systems, Electr. Notes Theor. Comput. Sci., 153(1), 2006, 55-75.
• [37] Ritchie, R.W.: Classes of predictably computable functions, Trans. Amer. Math. Soc., 106, 1963, 139-179.
• [38] Rogers Jr, H.: Theory of recursive functions and effective computability, MIT Press Cambridge, MA, USA, 1987.
• [39] Rose, H.: Subrecursion, Functions and Hierarchies, School of Mathematics, University of Bristol Edition, Clarendon Press, Oxford, 1984.
• [40] Rauszer, C. and Sabalski, B.: Notes on Rasiowa-Sikorski Lemma, Studia Logica, XXXIV, 3, 1975, 265-268.
• [41] Schwichtenberg, H.: Classifying recursive functions, Handbook of Recursion Theory, North Holland Elsevier, Amsterdam, 1997.
• [42] Shelah, S.: Primitive Recursive Bounds for Van Der Waerden Numbers, Journal of the American Mathematical Society, 1(3), 1988, 683-697.
• [43] Švejdar, V.: An Interpretation of Robinson Arithmetic in its Grzegorczyk's Weaker Variant, Fundamenta Informaticae, 81(1-3), 2007, 347-354.
• [44] Wagner, K., Wechsung, G.: Computational Complexity, Springer, 2001.
• [45] Wainer, S.: Ordinal Recursion, and a Refinement of the Extended Grzegorczyk Hierarchy, The Journal of Symbolic Logic, 37(2), June 1972, 281-292.
• [46] Weiermann, A.: Rewriting theory for the Hydra battle and the extended Grzegorczyk hierarchy, Technical report, 1995.
• [47] Wolter, F., Zakharyaschev, M.: Qualitative spatio-temporal representation and reasoning: a computational perspective, in: Exploring Artificial Intelligence in the New Millenium (G. Lakemeyer, B. Nebel, Eds.), Morgan Kaufmann, 2002, 175-216.