Complexity of simulation preorder for a product of finite automata
M. Grabowski · 2010
We consider complexity of the question whether a finite-state system simulates a product of finite-state systems. As the main technical result we show EXPTIME-hardness of that problem. However, the value of our result appears more apparent when related to the complexity of language inclusion, known to be in PSPACE for the case we study. Our hardness result thus provides a counterexample to a widely accepted conjecture that branching-time preorders tend to be more computationally tractable than the linear-time ones. To the best of our knowledge, this is the first such counterexample.