Miroslaw Kutylowski, papers

• [1]``Boolean operations over measure algebras'', joint work with A. Kamburelis, Coll. Math. 50.2 (1986).
  
  
• [2] ``Restricted comprehension and collection schemata in weak set theories'', Zt. math. Log. Grundlag. Math. 30.1 (1987).
  
  
• [3] ``Small Grzegorczyk classes and relations defined by simultaneous recursion and iteration'', Ph. D. Dissertation, Instytut Matematyki Uniwersytetu Wroclawskiego, 1984.
  
  
• [3a] ``Small Grzegorczyk classes'', the journal version of the Ph. D. Dissertation, the Journal of the London Mathematical Society, 36.2 (1987), 193-210.
  
  
• [4] ``A generalized Grzegorczyk hierarchy and low complexity classes'', Information and Computation 72.2 (1987), 133-149.
  
  
• [5] ``A note about E^0_*=E^2_*? problem'', joint work with K. Loryś, Zt. math. Logik und Grundlag. Math., 33 (1987).
  
  
• [6] ``Finite automata , real time processes and counting problem for bounded arithmetics'', the Journal of Symbolic Logic, 53.1 (1988), 243-258.
  
  
• [7] ``Chains of finite automata with bounded number of states'', Fundamenta Informaticae 11.3 (1988).
  
  
• [8] ``Reversal complexity classes for alternating Turing machines'', joint work with M. Liśkiewicz and K. Loryś, the SIAM Journal on Computing 19.2 (1990), 207-221.
  
  
• [9] ``MicroProlog - Opis jezyka programowania'', (``MicroProlog - Programming language manual'', in Polish) Wydawnictwo Uniwersytetu Wroclawskiego, 1989.
  
  
• [10]``Multihead one-way finite automata'', Theoretical Computer Science, 85 (1991), 135-153.
  
  
• [11]``One-way multihead finite automata and 2-bounded languages'', Mathematical Systems Theory, 23 (1990), 107-139.
  
  
• [12] ``Remarks on sorting and one-way multihead finite automata'', Information Processing Letters, 36 (1990), 215-218.
  
  
• [13] ``Time complexity of Boolean functions on PRAMs without simultaneous writes'', SIAM Journal on Computing, 20 (1991), 824-833.
  Abstract .
  
  
• [14]``Stack versus sensitivity for one-way automata'', Theoretical Computer Science, 119.2 (1993), 233-246.
  Abstract .
  
  
• [10a],[11a],[12a],[14a] ``Computational power of one-way multihead finite automata'', a conference paper exposing the results of papers [11]-[14], in Proceedings of the Symposium on Theoretical Aspects of Computer Science (1990), Lecture Notes in Computer Science 415, Eds. C. Choffrut and T. Lengauer, pp. 176-187.
  
  
• [15] ``Exact time bounds for computing Boolean functions on PRAMs without simultaneous writes'', joint work with M. Dietzfelbinger and R. Reischuk, Proceedings of 2nd ACM Symposium on Parallel Algorithms and Architectures (1990), pp. 125-135.
  Abstract .
  
  
• [16] ``Broadcasting information by exclusive read PRAMs'', joint paper with P. Beame and M. Kik, Parallel Processing Letters, 4.1&2 (1994), 159-169.
  Abstract .
  
  
• [17] ``Exact lower time bounds for Boolean functions on CREW PRAMs'', joint work with M. Dietzfelbinger and R. Reischuk, a journal version of the first part of the paper 15, Journal of Computer and System Sciences 48.2 (1994), 231-254.
  Abstract .
  
  
• [18] ``Feasible time-optimal algorithms for Boolean functions on exclusive read PRAMs'', joint work with M. Dietzfelbinger and R. Reischuk, enlarged version of the second part of paper [15], to appear in SIAM Journal on Computing (1996),
  Abstract .
  
  
• [19] ``Limits on the power of parallel random access machines with weak forms of write conflict resolution'', joint paper with F. Fich, R. Impagliazzo, B. Kapron and V. King, in STACS 93, 10th Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February'93, Proceedings, Lecture Notes in Computer Science 665, (Springer, Berlin, 1993), pp. 386-397.
  Journal version in Journal of Computer and System Sciences, 53.1 (1996) 104--111.
  
  
• [20] ``Fast merging on the EREW PRAM'', , joint paper with T. Hagerup, in Proc. of International Coll. on Automata Languages and Programming '92, Lecture Notes in Computer Science 623, (Springer, Berlin, 1992), pp. 318-329,
  a journal version accepted for Algorithmica.
  
  
• [21] ``Complexity of Boolean functions on PRAMs - lower bound techniques'', a survey paper, in Data Structures and Efficient Algorithms, B. Monien and Th. Ottman (eds.), Lecture Notes in Computer Science 594, (Springer, Berlin, 1992), pp. 309-329.
  
  
• [22] ``Sorting on 2-dimensional grids'', joint paper with R. Wanka, Parallel Processing Letters, 2.2 and 2.3 (1992), 213-220.
  Abstract .
  
  
• [23] ``Retrieval of scattered information by EREW, CREW and CRCW PRAMs'', joint paper with F. Fich, M. Kowaluk, K. Loryś and P. Ragde, in Algorithm Theory - SWAT'92, Lecture Notes in Computer Science 621, (Springer, Berlin, 1992), pp. 30-41, a journal version in Computational Complexity, 5 (1995), 113-131.
  
  
• [24] ``Playing Tetris on meshes and multi-dimensional SHEARSORT'', joint paper with R. Wanka, to appear in Algorithms and Computation, 8th International Symposium on Algorithms and Computation, Singapore, December'97, Proceedings, \rm Lecture Notes in Computer Science ????, (Springer, Berlin, 1997), ???--???. Abstract .
  
  
• [25] ``Periodic constant depth sorting networks'', joint work with M. Kik, G. Stachowiak, STACS 94, 11th Annual Symposium on Theoretical Aspects of Computer Science, Caen, France, February'94, Proceedings, Lecture Notes in Computer Science 775, (Springer, Berlin, 1994), 201-212.
  A full version in technical report:, tr-rf-93-007 , Universitat-GH Paderborn, Fachbereich Mathematik-Informatik, Forschergruppe Effiziente Nutzung Massiv Paralleler Systeme .
  
  
• [26] ``Approximate compaction and padded sorting on CREW PRAMs'', joint work with T. Wierzbicki, in IPPS'96, International Parallel Processing Symposium, (IEEE Press, 1996) 174-181.
  Preliminary version in technical report, tr-ri-95-160, Universitat-GH Paderborn, Fachbereich Mathematik-Informatik, Reihe Informatik
  
  
• [27] ``Fast and feasible periodic sorting networks of constant depth'', joint work with K. Loryś, B. Oesterdiekhoff, and R.  Wanka, in Proc. 35th IEEE Symposium on Foundations of Computer Science, 1994, pp. 369-380.
  Abstract .
  Full version of the first part of this paper in ``Constructing sorting networks with constant period.'', Technical report tr-ri-95-009 , Universitat-GH Paderborn, Fachbereich Mathematik-Informatik, Reihe Forschergruppe
  
  
• [28] ``Przydatność oceny hematologicznych wykladników infekcji w zapaleniu kości i stawów u noworodków'' (in Polish, ``Relevance of hematological analysis for diagnosis of bone and joint infections for infants''), joint work with Joanna Koralewska, Waldemar Maszkiewicz, poster presentation at 24 Polish Pediatric Symposium, Gdańsk 1995, poster number 125
  
  
• [29] ``Limitations of the QRQW and EREW PRAM models'', joint work with K. Loryś, Foundations of Software Technology and Theoretical Computer Science. Proc. 16th Conf., Hyderabad, India, Dec. 18-20, 1996, Lecture Notes in Computer Science 1180, (Springer, Berlin, 1996), 310-321.
  Also available in EBIT, 1996.
  
  
• [30] ``Fast generation of random permutations via network simulation'' joint work with A.Czumaj, K. Loryś, P.Kanarek, ESA'96, 4th Annual European Symposium on Algorithms, Barcelona 1996, Lecture Notes in Computer Science 1136, (Springer, Berlin, 1996), 246--260.
  A journal version accepted for Algorithmica.
  Technical report.
  Also available in EBIT, 1996.
  
  
• [31] ``Periodic merging networks'' joint work with B. Oesterdiekhoff, K. Loryś, ISAAC'96, 7th International Symposium on Algorithms and Computation, Osaka 1996.
  A journal version accepted for Theory of Computing Systems.
  Technical report.
  
  
• [32] ``Distributed mixing'' joint work with A.Czumaj, K. Loryś, P.Kanarek, manuscript, April 1997.
  
  
• [33] ``A lower bound for parity on randomized CRCW PRAMs'', joint work with Thomas Schwöppe, manuscript, September 1997.

  ---

  Textbooks

• [1] ``Informationstheorie, Codierung und Kryptologie'', joint work with W.Strothman, lecture notes (in German) , Paderborn, Fall 1995
  
  
• [2] ``Wyklady z Kryptografii'', joint work with Willy-B. Strothmann, textbook (in Polish) , Paderborn, April 1997
  Also available in EBIT, 1997.