Jančar, Petr; Osička, Petr; Sawa, Zdeněk EXPSPACE-complete variant of countdown games, and simulation on succinct one-counter nets. (English) Zbl 06963050 Potapov, Igor (ed.) et al., Reachability problems. 12th international conference, RP 2018, Marseille, France, September 24–26, 2018. Proceedings. Cham: Springer (ISBN 978-3-030-00249-7/pbk; 978-3-030-00250-3/ebook). Lecture Notes in Computer Science 11123, 59-74 (2018). MSC: 68Qxx PDF BibTeX XML Cite \textit{P. Jančar} et al., Lect. Notes Comput. Sci. 11123, 59--74 (2018; Zbl 06963050) Full Text: DOI
Czerwiński, Wojciech; Jančar, Petr; Kot, Martin; Sawa, Zdeněk Complexity of checking bisimilarity between sequential and parallel processes. (English) Zbl 1398.68361 Chatterjee, Krishnendu (ed.) et al., Mathematical foundations of computer science 2013. 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26–30, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40312-5/pbk). Lecture Notes in Computer Science 8087, 302-313 (2013). MSC: 68Q85 68Q25 PDF BibTeX XML Cite \textit{W. Czerwiński} et al., Lect. Notes Comput. Sci. 8087, 302--313 (2013; Zbl 1398.68361) Full Text: DOI
Sawa, Zdeněk Efficient construction of semilinear representations of languages accepted by unary nondeterministic finite automata. (English) Zbl 1281.68146 Fundam. Inform. 123, No. 1, 97-106 (2013). MSC: 68Q45 PDF BibTeX XML Cite \textit{Z. Sawa}, Fundam. Inform. 123, No. 1, 97--106 (2013; Zbl 1281.68146) Full Text: DOI
Jančar, Petr; Kot, Martin; Sawa, Zdeněk Complexity of deciding bisimilarity between normed BPA and normed BPP. (English) Zbl 1209.68338 Inf. Comput. 208, No. 10, 1193-1205 (2010). MSC: 68Q85 PDF BibTeX XML Cite \textit{P. Jančar} et al., Inf. Comput. 208, No. 10, 1193--1205 (2010; Zbl 1209.68338) Full Text: DOI
Sawa, Zdeněk Efficient construction of semilinear representations of languages accepted by unary NFA. (English) Zbl 1287.68100 Kučera, Antonín (ed.) et al., Reachability problems. 4th international workshop, RP 2010, Brno, Czech Republic, August 28–29, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15348-8/pbk). Lecture Notes in Computer Science 6227, 176-182 (2010). MSC: 68Q45 68Q25 PDF BibTeX XML Cite \textit{Z. Sawa}, Lect. Notes Comput. Sci. 6227, 176--182 (2010; Zbl 1287.68100) Full Text: DOI
Fröschle, Sibylle; Jančar, Petr; Lasota, Slawomir; Sawa, Zdeněk Non-interleaving bisimulation equivalences on basic parallel processes. (English) Zbl 1185.68444 Inf. Comput. 208, No. 1, 42-62 (2010). MSC: 68Q85 PDF BibTeX XML Cite \textit{S. Fröschle} et al., Inf. Comput. 208, No. 1, 42--62 (2010; Zbl 1185.68444) Full Text: DOI
Sawa, Zdeněk; Jančar, Petr Hardness of equivalence checking for composed finite-state systems. (English) Zbl 1166.68018 Acta Inf. 46, No. 3, 169-191 (2009). MSC: 68Q17 68Q85 PDF BibTeX XML Cite \textit{Z. Sawa} and \textit{P. Jančar}, Acta Inf. 46, No. 3, 169--191 (2009; Zbl 1166.68018) Full Text: DOI
Jančar, Petr; Kot, Martin; Sawa, Zdeněk Normed BPA vs. normed BPP revisited. (English) Zbl 1160.68468 van Breugel, Franck (ed.) et al., CONCUR 2008 – concurrency theory. 19th international conference, CONCUR 2008, Toronto, Canada, August 19–22, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85360-2/pbk). Lecture Notes in Computer Science 5201, 434-446 (2008). MSC: 68Q85 68Q60 PDF BibTeX XML Cite \textit{P. Jančar} et al., Lect. Notes Comput. Sci. 5201, 434--446 (2008; Zbl 1160.68468) Full Text: DOI
Jančar, Petr; Sawa, Zdeněk A note on emptiness for alternating finite automata with a one-letter alphabet. (English) Zbl 1184.68317 Inf. Process. Lett. 104, No. 5, 164-167 (2007). MSC: 68Q45 PDF BibTeX XML Cite \textit{P. Jančar} and \textit{Z. Sawa}, Inf. Process. Lett. 104, No. 5, 164--167 (2007; Zbl 1184.68317) Full Text: DOI
Kot, Martin; Sawa, Zdeněk Bisimulation equivalence of a BPP and a finite-state system can be decided in polynomial time. (English) Zbl 1272.68309 Bradfield, Julian (ed.) et al., Proceedings of the 6th international workshop on verification of infinite-state systems (INFINITY 2004), London, UK, September 4, 2004. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 138, No. 3, 49-60 (2005). MSC: 68Q85 68Q25 PDF BibTeX XML Cite \textit{M. Kot} and \textit{Z. Sawa}, Electron. Notes Theor. Comput. Sci. 138, No. 3, 49--60 (2005; Zbl 1272.68309) Full Text: Link
Sawa, Zdeněk; Jančar, Petr Behavioural equivalences on finite-state systems are PTIME-hard. (English) Zbl 1109.68052 Comput. Inform. 24, No. 5, 513-528 (2005). MSC: 68Q25 68Q10 68Q85 93A30 PDF BibTeX XML Cite \textit{Z. Sawa} and \textit{P. Jančar}, Comput. Inform. 24, No. 5, 513--528 (2005; Zbl 1109.68052)
Jančar, Petr; Kučera, Antonín; Moller, Faron; Sawa, Zdeněk DP lower bounds for equivalence-checking and model-checking of one-counter automata. (English) Zbl 1078.68087 Inf. Comput. 188, No. 1, 1-19 (2004). MSC: 68Q45 68Q60 PDF BibTeX XML Cite \textit{P. Jančar} et al., Inf. Comput. 188, No. 1, 1--19 (2004; Zbl 1078.68087) Full Text: DOI
Sawa, Zdeněk Equivalence checking of non-flat systems is EXPTIME-hard. (English) Zbl 1274.68134 Amadio, Roberto (ed.) et al., CONCUR 2003 – concurrency theory. 14th international conference, Marseille, France, September 3–5, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40753-7/pbk). Lect. Notes Comput. Sci. 2761, 237-250 (2003). MSC: 68Q17 68Q45 68Q60 68Q85 PDF BibTeX XML Cite \textit{Z. Sawa}, Lect. Notes Comput. Sci. 2761, 237--250 (2003; Zbl 1274.68134) Full Text: DOI
Jančar, Petr; Kučera, Antonín; Moller, Faron; Sawa, Zdeněk Equivalence-checking with one-counter automata: A generic method for proving lower bounds. (English) Zbl 1077.68653 Nielsen, Mogens (ed.) et al., Foundations of software science and computation structures. 5th international conference, FOSSACS 2002, held as part of the joint European conferences on theory and practice of software, ETAPS 2002, Grenoble, France, April 8–12, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43366-X). Lect. Notes Comput. Sci. 2303, 172-186 (2002). MSC: 68Q17 68Q45 68Q85 PDF BibTeX XML Cite \textit{P. Jančar} et al., Lect. Notes Comput. Sci. 2303, 172--186 (2002; Zbl 1077.68653) Full Text: Link
Sawa, Zdenek; Jančar, Petr P-hardness of equivalence testing on finite-state processes. (English) Zbl 1052.68093 Pacholski, Leszek (ed.) et al., SOFSEM 2001: Theory and practice of informatics. 28th conference on current trends in theory and practice of informatics, Piešt’any, Slovak Republic, November 24 – December 1, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42912-3). Lect. Notes Comput. Sci. 2234, 326-335 (2001). MSC: 68Q85 68Q17 PDF BibTeX XML Cite \textit{Z. Sawa} and \textit{P. Jančar}, Lect. Notes Comput. Sci. 2234, 326--335 (2001; Zbl 1052.68093) Full Text: Link
Jančar, Petr; Moller, Faron; Sawa, Zdeněk Simulation problems for one-counter machines. (English) Zbl 0963.68094 Pavelka, Jan (ed.) et al., SOFSEM ’99: Theory and practice of informatics. 26th conference on Current trends in theory and practice of informatics. Milovy, Czech Republic, November 27-December 4, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1725, 404-413 (1999). MSC: 68Q45 PDF BibTeX XML Cite \textit{P. Jančar} et al., Lect. Notes Comput. Sci. 1725, 404--413 (1999; Zbl 0963.68094)