Publications of Zdeněk Sawa

Journal papers:

• Efficient Construction of Semilinear Representations of Languages Accepted by Unary Nondeterministic Finite Automata
  Zdeněk Sawa
  Fundamenta Informaticae, Volume 123, Number 1, pp. 97-106, IOS Press, 2013.
  DOI: 10.3233/FI-2013-802
  PostScript, PDF (10 pages)
  
  
• Complexity of deciding bisimilarity between normed BPA and normed BPP
  Petr Jančar, Martin Kot, and Zdeněk Sawa
  Information and Computation, Special Issue: 19th International Conference on Concurrency Theory (CONCUR 2008), Volume 208, Issue 10, pp. 1193-1205, Elsevier, 2010.
  DOI: 10.1016/j.ic.2009.10.012
  PostScript, PDF (28 pages)
  
  
• Non-Interleaving Bisimulation Equivalences on Basic Parallel Processes
  Sibylle Fröschle, Petr Jančar, Slawomir Lasota, and Zdeněk Sawa
  Information and Computation, Volume 208, Issue 1, pp. 42-62, Elsevier, 2010.
  DOI: 10.1016/j.ic.2009.06.001
  PostScript, PDF (37 pages)
  
  
• Hardness of equivalence checking for composed finite-state systems
  Zdeněk Sawa and Petr Jančar
  Acta Informatica, Volume 46, Number 3, pp. 169-191, Springer, 2009.
  DOI: 10.1007/s00236-008-0088-x
  PostScript, PDF (28 pages)
  
  
• A note on emptiness for alternating finite automata with a one-letter alphabet
  Petr Jančar and Zdeněk Sawa
  Information Processing Letters 104 (5), pp. 164-167, Elsevier, 2007.
  DOI: 10.1016/j.ipl.2007.06.006
  PostScript, PDF (6 pages)
  
  
• Behavioural Equivalences on Finite-State Systems are PTIME-hard
  Zdeněk Sawa and Petr Jančar
  Computing and Informatics 24 (5), pp. 513-528, Slovak Academy of Sciences, Institute of Informatics, 2005.
  PostScript, PDF (20 pages)
  
  
• DP lower bounds for equivalence-checking and model-checking of one-counter automata
  Petr Jančar, Antonín Kučera, Faron Moller, and ZdeněkSawa
  Information and Computation 188 (1), pp. 1-19, Elsevier, 2004.
  PostScript, PDF (19 pages)
  
  

Conferance papers:

• Complexity of Checking Bisimilarity between Sequential and Parallel Processes
  Wojciech Czerwiński, Petr Jančar, Martin Kot, and Zdeněk Sawa
  Mathematical Foundations of Computer Science 2013, Lecture Notes in Computer Science 8087, pp. 302-313, Springer, 2013.
  The final publication is available at link.springer.com.
  DOI: 10.1007/978-3-642-40313-2_28
  PostScript, PDF (12 pages)
  
  
• Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA
  Zdeněk Sawa
  4th International Workshop on Reachability Problems (RP 2010), Lecture Notes in Computer Science 6227, pp. 176-182, LNCS 6227, Springer, 2010.
  Postscript, PDF (7 pages)
  
  
• Normed BPA vs. Normed BPP Revisited
  Petr Jančar, Martin Kot, and Zdeněk Sawa
  In Proceedings of CONCUR 2008 (Toronto, Canada, August 2008), Lecture Notes in Computer Science 5201, pp. 434-446, Springer, 2008.
  Postscript, PDF (14 pages)
  
  
• History Preserving Bisimilarity on Basic Parallel Processes
  Zdeněk Sawa and Petr Jančar
  In Proceedings of TAAPSD'06, Kiev, pp. 9-14, 2006.
  
  
• On Distributed Bisimilarity over Basic Parallel Processes
  Petr Jančar and Zdeněk Sawa
  In Proceedings of workshop AVIS 2005 (A Satellite Workshop of ETAPS 2005), 2005.
  PostScript, PDF (15 pages)
  
  
• Bisimulation Equivalence of a BPP and a Finite State System can be Decided in Polynomial Time
  Martin Kot and Zdeněk Sawa
  In Proceedings of Infinity 2004 (A Satellite Workshop of CONCUR 2004), 2004.
  PostScript, PDF (11 pages)
  
  It was later published (together with other papers from Infinity 2004) in Electronic Notes in Theoretical Computer Science 138, pp. 49-60, Elsevier, 2005.
  It is available on ENTCS page.
  
  
• Equivalence Checking of Non-flat Systems Is EXPTIME-hard
  Zdeněk Sawa
  In Proceedings of CONCUR 2003 (Marseille, France, September 2003), Lecture Notes in Computer Science, 2761, pp. 237-250, Springer, 2003.
  Postscript, PDF (15 pages)
  
  
• Equivalence-Checking with One-Counter Automata: A Generic Method for Proving Lower Bounds.
  Petr Jančar, Antonín Kučera, Faron Moller, and Zdeněk Sawa
  In Proceedings of FOSSACS 2002 (Grenoble, France, April 2002), Lecture Notes in Computer Science 2303, pp. 173-187, Springer, 2002.
  PostScript, PDF (15 pages)
  
  
• P-hardness of Equivalence Testing on Finite-State Processes.
  Zdeněk Sawa and Petr Jančar
  In Proceedings of SOFSEM 2001 (Piešťany, Slovak Rep., November 2001), Lecture Notes in Computer Science, 2234, pp. 326, Springer, 2001.
  PostScript, PDF (20 pages)
  
  
• Simulation Problems for One-Counter Machines.
  Petr Jančar, Faron Moller, and Zdeněk Sawa
  In Proceedings of SOFSEM'99 (Milovy, Czech Rep., November 1999), Lecture Notes in Computer Science 1725, pp. 404-413, Springer, 1999.
  PostScript, PDF (15 pages)
  
  

Ph.D. Thesis:

• Complexity and Decidability of Some Equivalence-Checking Problems
  Zdeněk Sawa
  Ph.D. Thesis, 2005.
  PostScript, PDF (116 pages)

Habilitation Thesis:

• Computational Complexity of Some Equivalence-Checking Problems
  Zdeněk Sawa
  Habilitation Thesis, 2013.
  PostScript, PDF (91 pages)

Some other texts:

• Complexity of Equivalence Checking Problems
  Zdeněk Sawa
  Proceedings of Ph.D. workshop WOFEX 2003, VŠB-TU Ostrava, 2003.
  PostScript, PDF (6 pages)
  
  
• Equivalence problems for finite-state and one-counter processes.
  Zdeněk Sawa
  Outline of the thesis, 2000.
  PostScript, PDF (16 pages)
  
  
• P-úplnost: těžko paralelizovatelné problémy. (in czech)
  Zdeněk Sawa
  2000.
  PostScript, PDF (15 pages)
  
  
• Algoritmy používané pro kompresi dat. (in czech)
  Zdeněk Sawa
  2000.
  PostScript, PDF (20 pages)
  
  
• Bezkontextové grafové gramatiky. (in czech)
  Zdeněk Sawa
  1999.
  PostScript, PDF (20 pages)