Publications

Jurek Tyszkiewicz

2000

  • E. Rosen and J. Tyszkiewicz. {SO$(\forall\exists^*)$ sentences and their asymptotic probabilities}. Mathematical Logic Quarterly, vol. 46, pp. 435–52, 2000.                                 

1999

  • F. Neven, M. Otto, J. Tyszkiewicz, and V. den Bussche. Adding FOR-Loops to First-Order Logic. In Proceedings of ICDT'99, vol. 1540 of LNCS, pp. 58–69. Springer, 1999.             

1998

  • J. Tyszkiewicz. On the Kolmogorov Expressive Power of Boolean Query Languages. Theoretical Computer Science, vol. 190, pp. 317–361, 1998.                                 

1997

  • P. Idziak and J. Tyszkiewicz. Monadic Second Order Probabilities in Algebra. Directly Representable Varieties and Groups. In Logic and Random Structures, AMS (R. B. Boppana and J. F. Lynch, Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, pp. 79–108, 1997.             
  • J. Tyszkiewicz. The Kolmogorov Expression Complexity of Logics. Information and Computation, vol. 135, pp. 113–135, 1997.                                 
  • J. Tyszkiewicz. A Note on the Kolmogorov Data Complexity and Nonuniform Logical Definitions. Information Processing Letters, vol. 64, pp. 187–195, 1997.                                 
  • J. Tyszkiewicz. Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines. Fundamenta Informaticae, vol. 32, pp. 91–105, 1997.                                 
  • J. Tyszkiewicz. Fine Hierarchies of Generic Computation. In Proceedings of International Conference in Database Theory ICDT `97 (F. Afrati and P. Kolaitis, Eds.), vol. 1186 of LNCS, pp. 125–139. Springer, 1997.                                 

1995

  • J. Tyszkiewicz. Probabilities in First-Order Logic of a Unary Function and a Binary Relation. Random Structures and Algorithms, vol. 6, pp. 181–191, 1995.                                 

1994

  • J. Tyszkiewicz. Infinitary queries and their asymptotic probabilities II: properties definable in least fixed point logic. Random Structures and Algorithms, vol. 5, pp. 215–234, 1994.                                 

1993

  • J. Tyszkiewicz. On Asymptotic Probabilities in Logics That Capture DSPACE($łog n$) in Presence of Ordering. In Proceedings of TAPSOFT `93, vol. 668 of LNCS, pp. 569–583. Springer, 1993.                                 
  • J. Tyszkiewicz. On Asymptotic Probabilities of Monadic Second Order Properties. In Computer Science Logic, 6th Workshop, CSL `92, San Miniato 1992, Selected Papers (E. Börger, G. Jäger, H. K. Büning, S. Martini, and M. M. Richter, Eds.), vol. 702 of LNCS, pp. 425–439. Springer, 1993.                                 

1991

  • J. Tyszkiewicz. Infinitary Queries and Their Asymptotic Probabilities I: Properties Definable in Transitive Closure Logic. In Proceedings of Workshop on Computer Science Logic CSL {`91}, vol. 626 of LNCS, pp. 396–410. Springer, 1991.