A Rice-style theorem for parallel automata
We present a general result, similar to Rice's theorem, concerning the complexity of detecting properties on finite automata enriched by bounded cooperative concurrency, such as statecharts and abstract parallel automata, which we denote by CFAs (Concurrent Finite Automata). On one extreme, the complexity of detecting non-trivial properties that preserve equivalence of machines, i.e., properties of the accepted language, on finite automata, can be as little as O(1). On the other extreme, Rice's theorem states that all such properties on Turing machines are undecidable. We state that all the non-trivial properties of the regular (or omega-regular) languages, are PSPACE-hard on CFAs with epsilon-moves and on CFAs without E-moves accepting infinite words. We also extend this result to CFAs without epsilon-moves accepting finite words that satisfy a condition that holds for many properties. (c) 2008 Elsevier Inc. All rights reserved.
parallel automata rice's theorem statecharts pspace-hard regular languages