Computational Complexity of Some Equivalence-Checking Problems
Zdenÿek Sawa · 2012
This habilitation thesis gives an overview of five papers of the author in the area of verification, in particular, in the study of computational complexity of equivalence checking problems and related areas. The first of these papers, Sawa, Jancar: Equivalences on Finite-State Systems are PTIME-hard (2005), shows that deciding any relation between bisimulation equivalence (bisimilarity) and trace preorder is PTIME-hard for finite-state systems that are presented explicitly (i.e., as a list of states and transitions). The second paper, Sawa, Jancar: Hardness of equivalence checking for composed finite-state systems (2009), gives a proof that deciding any relation between bisimulation equivalence and trace preorder is EXPTIME-hard for systems composed of interacting finite-state components. Further hardness results are shown for special cases of acyclic systems. The third paper, Jancar, Kot, Sawa: Complexity of deciding bisimilarity between normed BPA and normed BPP (2010), presents a polynomial-time algorithm deciding bisimilarity between a normed BPA process and a normed BPP process, with running time O(n). The forth paper, Froschle, Jancar, Lasota, Sawa: Non-Interleaving Bisimulation Equivalences on Basic Parallel Processes (2010), describes polynomial time algorithms for deciding hereditary history preserving bisimilarity (in O(n logn)) and history preserving bisimilarity (in O(n)) on BPP processes. The fifth paper, Jancar, Sawa: A note on emptiness for alternating finite automata with a one-letter alphabet (2007) gives a short direct self-contained proof of PSPACE-hardness of the emptiness problem for alternating finite automata with a singleton alphabet, which is much simpler than the original proof by Holtzer (1995) relying on a series of reductions from several papers.