Andrzej Szepietowski

Uniwersytet Gdański
Instytut Informatyki
Wita Stwosza 57
80-952 Gdansk
Poland

e-mail: matszp@inf.ug.edu.pl

Interest:

Latest technical reports:

  1. A. Szepietowski, Fault-tolerant pancyclicity in alternating group graphs, 2010, download pdf

Books:

Papers

  1. A. Szepietowski, A finite 5-pebble-automaton can search every maze,
    Information Processing Letters 15 (1982) 5, 199--204.
  2. A. Szepietowski, On searching plane labyrinths by 1-pebble automata,
    Elektronische Informationsverarbeitung und Kybernetik (Journal of Information Processing and Cybernetics) 19 (1983) 1/2, 79--84.
  3. A. Szepietowski, Remarks on searching labyrinths by automata
    in: M. Karpiński ed., Foundations of Computation Theory, Proc. of the 1983 International FCT-Conference, Borgholm, Sweden, August 1983
    Lecture Notes in Computer Science Vol. 158 (Springer, Berlin, 1983) 457--464.
  4. A. Szepietowski, On Paterson's problem
    Elektronische Informationsverarbeitung und Kybernetik (Journal of Information Processing and Cybernetics) 21 (1985) 6, 313--314.
  5. A. Szepietowski, There are no fully space constructible functions between log(log(n)) and log(n)
    Information Processing Letters 24 (1987) 361--362.
  6. A. Szepietowski, Remarks on languages acceptable in log(log(n)) space,
    Information Processing Letters 27 (1988) 201--203.
  7. A. Szepietowski, On three-way two-dimensional Turing machines
    Information Sciences 47 (1989) 2, 135--147.
  8. A. Szepietowski, Some remarks on alternating hierarchy and closure under complement for sublogarithmic space
    Information Processing Letters 33 (1989/90) 73--78.
  9. A. Szepietowski, Some notes on strong and weak log(log(n)) space complexity
    Information Processing Letters 33 (1989/90) 109--112.
  10. A. Szepietowski, If deterministic and nondeterministic space complexities are equal for log(log(n)) then they are also equal for log(n)
    Theoretical Computer Science 74 (1990) 115--119.
  11. A. Szepietowski Weak mode of space complexity can be used in the proof that [DSPACE(log(log(n))=NSPACE(log(log(n))]==>[L=NL]
    Bulletin of the European Association for Theoretical Computer Science, EATCS No. 40, February 1990, 266--269.
  12. A. Szepietowski, On three-way two-dimensional multicounter automata
    Information Sciences 55 (1991) 35--47.
  13. A. Szepietowski, On space functions constructed by two-dimensional Turing machines,
    Information Sciences 60 (1992) 177--183.
  14. A. Szepietowski, Some remarks on two-dimensional finite automata,
    Information Sciences 63 (1992) 183--189.
  15. A. Szepietowski, Two-dimensional on-line tessellation acceptors are not closed under complement,
    Information Sciences 64 (1992) 115--120.
  16. A. Szepietowski, The element distinctness problem on one-tape Turing machines
    Information Processing Letters 59 (1996) 203--206.
  17. A. Szepietowski, Weak and strong one-way space complexity classes
    Information Processing Letters 67 (1998) 299--302.
  18. A. Szepietowski, There is no complete axiom system for shuffle expressions
    RAIRO, Theoretical Informatics and Applications, 33 (1999) 271--277.
  19. A. Szepietowski, Lower space bounds for accepting shuffle languages
    RAIRO, Theoretical Informatics and Applications, 33 (1999) 303--307.
  20. J. Jędrzejowicz, A. Szepietowski, Shuffle languages are in P,
    Theoretical Computer Science 250 (2001) 31--53.
  21. R. Fidytek, A.W. Mostowski, R. Somla, Algorithms counting monotone Boolean functions
    Information Processing Letters, 79 (2001) 203--209.
  22. J. Jędrzejowicz, A. Szepietowski, On the expressive power of the shuffle operator matched with intersection by regular sets
    RAIRO, Theoretical Informatics and Applications 35 (2001) 379-388.
  23. J. Neumann, A. Szepietowski, I. Walukiewicz,Complexity of weak acceptance conditions in tree automata
    Information Processing Letters 84 (2002) 181-187.
  24. A.Szepietowski, M. Targan, A note on the oriented chromatic number of grids
    Information Processing Letters 92 (2004) 65-70.
  25. A.Szepietowski, A note on alternating one-pebble Turing machines with sublogarithmic space
    Information Processing Letters 98 (2006) 174 -176.
  26. A.Szepietowski, Fooling turing machines with sublogarithmic space: a note on 'for completeness, sublogarithmic space is no space' by M. Agrawal,
    Information Processing Letters 106 (2008) 162-163.
  27. A.Szepietowski, Fault-tolerant edge and vertex pancyclicity in alternating group graph
    Applied Mathematics and Computation 217 (2010) 2827--2832.
  28. A.Szepietowski, Fault tolerance of vertex pancyclicity in alternating group graphs
    Applied Mathematics and Computation 217 (2011)16, 6785-6791
  29. A. Szepietowski, Closure properties of hyper-minimized automata
    RAIRO, Theoretical Informatics and Applications 45 (2011) 459-466
  30. A. Szepietowski, Fault tolerance of edge pancyclicity in alternating group graphs,
    Applied Mathematics and Computation 218 (2012) 9875-9881
  31. A. Szepietowski, Hamiltonian cycles in hypercubes with 2n-4 faulty edges
    accepted for Information Sciences.