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)