Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
    informatyka analityczna  
UJ coat of arms
Foundations of Computer Science

Marek Zaionc


phone: (48 12) 664 6649
fax: (+48-12) 664 66 72
email: email
office: ul. Łojasiewicza 6, 30-348 Kraków
room: 3066
office hours: Tuesday 10:00 - 11:30 room 3066
Thursday 10:00 - 11:00
personal homepage
for students

research interests
logics of programs,
logic programming, functional programming.
asymptotic probability in logic, computability theory,

selected publications
  • M. Bendkowski, K. Grygiel, M. Zaionc, "Asymptotic Properties of Combinatory Logic", 12th Annual Conference on Theory and Applications of Models of Computation, LECTURE NOTES IN COMPUTER SCIENCE 9076 (2015), pp 62-72.
  • R. David, C. Raffalli, G. Theyssier, K. Grygiel, J. Kozik, M. Zaionc,
    "Asymptotically almost all $λ$-terms are strongly normalizing",
    Logical Methods in Computer Science, Vol. 9 (1:02) 2013, pp. 1–30
  • Katarzyna Grygiel, Pawel M. Idziak and Marek Zaionc,
    "How big is BCI fragment of BCK logic",
    Journal of Logic and Computation (2013), 23(3), pp 673-691
  • Herve Fournier, Daniele Gardy, Antoine Genitrini, Marek Zaionc,
    "Tautologies over implication with negative literals",
    Mathematical Logic Quarterly, 56, No. 4, pp388 – 396 (2010)
  • Rene David, Marek Zaionc,
    "Counting proofs in propositional logic",
    Archive for Mathematical Logic, Volume 48, Number 2, 2009, pp 185-199.
  • Zofia Kostrzycka, Marek Zaionc
    "Asymptotic densities in logic and type theory",
    Studia Logica vol 88 (2008) pp385-403
  • Herve Fournier, Daniele Gardy, Antoine Genitrini, Marek Zaionc
    "Classical and intuitionistic logic are asymptotically identical",
    Computer Science Logic 2007, Lecture Notes in Computer Science 4646, pp 177-193.
  • Lidia Badura, Marek Zaionc,
    "Parametrizability by regular expressions for equations on words",
    Bulletin of the Section of Logic, Vol. 36:1/2 (2007) pp 79 - 93.
  • Antoine Genitrini, Jakub Kozik, Marek Zaionc
    "Intuitionistic vs. Classical Tautologies, Quantitative Comparison",
    Lecture Notes in Computer Science 4941, (2008) pp. 100-109.
  • Marek Zaionc,
    "Probability distribution for simple tautologies",
    Theoretical Computer Science, Vol. 355, Issue 2, 2006 pp. 243-260
  • Marek Zaionc,
    "On the asymptotic density of tautologies in logic of implication and negation",
    Reports on Mathematical Logic vol. 39 (2005), pp 67 - 87.
  • Marek Zaionc,
    "Probabilistic approach to the lambda definability for fourth order types",
    Electronic Notes in Theoretical Computer Science, vol 140 (2005) pp 41-54.
  • Zofia Kostrzycka, Marek Zaionc,
    "Statistics of intuitionistic versus classical logics",
    Studia Logica, vol 76, (3) 2004, pp307 - 328.
  • Zofia Kostrzycka, Marek Zaionc,
    "On the density of truth in Dummet logic",
    Bulletin of the Section of Logic, vol. 32/1 (2003) pp 43-55.
  • Marek Zaionc,
    "Statistics of implicational logic",
    Electronic Notes in Theoretical Computer Science, volume 84 ,(2003)
  • Malgorzata Moczurad, Jerzy Tyszkiewicz, Marek Zaionc,
    "Statistical properties of simple types"
    Mathematical Structures in Computer Science, vol 10 (5) (2000), pp 575-594.
  • Jan Malolepszy , Malgorzata Moczurad, Marek Zaionc,
    "Schwichtenberg style lambda definability is undecidable",
    Lecture Notes in Computer Science 1210, April 1997, pp267-283.
  • Marek Zaionc,
    "Lambda representations of operations between different term algebras"
    Lecture Notes in Computer Science 933, June 1995 pp 91 - 105.
  • Marek Zaionc,
    "Lambda definability on free algebras",
    Annals of Pure and Applied logic 51 (1992) North-Holland, pp 279-300.
  • Marek Zaionc,
    "A Characterization of Lambda Definable Tree Operations",
    Information and Computation Vol. 89, No. 1, 1990. Academic Press, pp 35-46
  • Marek Zaionc,
    "How To Define Functionals on Free Structures in Typed lambda Calculus",
    Lecture Notes in Computer Science 379 Springer - Verlag, August 1989, pp 566-576.
  • Marek Zaionc,
    "On the lambda definable higher-order boolean functionals",
    Fundamenta Informaticae XII (1989) North-Holland, pp 181-190.
  • Marek Zaionc,
    "On the lambda definable tree operations",
    Lecture Notes in Computer Science 425, Springer-Verlag, June 1988, pp 279-292.
  • Marek Zaionc,
    "Mechanical Procedure for Proof Construction via Closed Terms in Typed lambda Calculus",
    Journal of Automated Reasoning 4 (1988), Reidel Publ, pp 173-190.
  • Marek Zaionc,
    "The Regular Expression Descriptions of Unifier Sets in the Typed lambda Calculus",
    Fundamenta Informaticae X (1987) North-Holland pp 309-322.
  • Marek Zaionc,
    "Word Operations Definable in the Typed lambda Calculus",
    Theoretical Computer Science 52 (1987) North-Holland pp 1-14.
  • Marek Zaionc,
    "The set of Unifiers in Typed lambda calculus as Regular Expression",
    Lecture Notes in Computer Science 202, Springer-Verlag, May 1985, pp 430-440.
  • Marek Zaionc,
    "Nondeterministic Programs Definable in Typed Lambda Calculus",
    Fundamenta Informaticae VIII.1 (1985) pp 63-72.
  • Marian Mrozek, Marek Zaionc,
    "A computer model of evolution and ecological processes",
    Modeling, Simulation & Control C, vol 1 Nr. 3 1984 pp 59-63.
  • Marian Mrozek, Marek Zaionc,
    "Simulation model of evolution in simplified ecological system",
    Wiadomosci ekologiczne, vol. XXVII 1981 nr 1, pp 49-59, (In Polish, English summary)

  • some recent collaborators 
    Rene DavidUniversite de Savoie, Chambery, France
    Daniele GardyUniversité de Versailles Saint-Quentin, France

    1992 - 1995 Computer Science in Krakow
      UE project TEMPUS
    1993 - 1995 Higher order lambda definability
      Ministry of Science and Higher Education
    1999 - 2000 Simple typed lambda calculs as a tool for higher order programming
      Ministry of Science and Higher Education
      8 T11C 018 16
    2001 - 2001 Support for Fifth International Conference of Typed Lambda Calculi and Applications
      Office of Naval Research, Pentagon, USA
    2001 - 2003 Object complexity amd asymptotic density
      Ministry of Science and Higher Education
      7 T11C 022 21
    2001 - 2003 Project LAMBDA, recherche coopérative en logique.
      EU grant, region Rhone-Alpes
    2004 - 2005 Project MIKOLAJ, recherche coopérative en logique computationnelle
      EU grant, region Rhone-Alpes
    2004 - 2006 Types for programs and proofs
      EU, szósty program ramowy
      Project of 35 European Universities,
      contract number 510996.
    2006 - 2008 Quantitative research in logic and functional languages
      POLONIUM grant
      Cooperation between TCS and L Ecole Normale Superieure de Lyon and Universite de Versailles Saint-Quentin.
    2008 - 2009 CASIMIR: Recherche coopérative en logique computationnelle
      Region Rhone-Alpes (France)
      Cooperation between Theoretical Computer Science Department and L Ecole Normale Superieure de Lyon.
      2008 - 0042, 0842C312
    2009 - 2012 Quantitative study in logics and computation theory
      Ministry of Science and Higher Education
      N206 3761 37
    2010 - 2012 Movement tracking in monitored zones
      Ministry of Science and Higher Education
      R00 0081 11
    2011 - 2012 Quantitative logic
      Ministry of Science and Higher Education,
    2014 - 2017 Kolonoskopia -Innowacyjna diagnostyka
    2014 - 2017 Asymptotic methods in lambda calculus and combinatory logic

    short cv
    1977Master of Science in MathematicsJagiellonian UniversityKrakw, Poland
    1985PhD in mathematics University of WarsawWarsaw, Poland
    19861986-1988, visiting prof. at Department of Computer Science The University of AlabamaBirmingham, USA
    1993 Habilitation Jagiellonian UniversityKrakow, Poland.
    1994 Visiting ProfessorTechnical University of AthensAthens, Greece.
    1994 Visiting Professor, Computer Science Department,Institute National des TellecommunicationsParis, France.
    1995 One month visit at Mathematics Department University of Swansea Swansea, UK
    1995Visiting Professor, Computer Science Department,University of Buffalo,Buffalo, New York, USA
    2002One month visit at Computer Science Department,L Ecole Normale Superieure,Lyon, France.
    2003 Deputy dean of the Faculty of Mathematics and Computer Science.Jagiellonian University Krakow, Poland.
    2006Professor of Mathematical SciencesJagiellonian UniversityKrakow, Poland
    2006Visiting prof. at Computer Science Department,Universite de Versailles, France.
    2007One month visit at Mathematics Department at Universite de SavoieChambery, France
      webmaster: email = a@b, a=www-tcs,