Communicating Hierarchical State Machines
作者： Rajeev Alur , Sampath Kannan , Mihalis Yannakakis
关键词:
摘要: Hierarchical state machines are finite whose states themselves can be other machines. In spite of their popularity in many modeling tools for software design, very little is known concerning complexity and expressiveness. this paper, we study these questions hierarchical as well communicating machines, that is, extended with both hierarchy concurrency. We present a comprehensive set results characterizing (1) the reachability, emptiness universality problems, (2) language inclusion equivalence (3) succinctness relationships between different types
springer.com
core.ac.uk
acm.org 
sci-hub.st 参考文章(12)
Garth Gullekson, Bran Selic, Paul Ward, Real-time object oriented modeling and design ,(1994)
Garth Gullekson, Bran Selic, Paul T. Ward, Real-time object-oriented modeling ,(1994)
Edmund M. Clarke, E. Allen Emerson, Design and Synthesis of Synchronization Skeletons Using Branching-Time Temporal Logic Logic of Programs, Workshop. pp. 52- 71 ,(1981) , 10.1007/BFB0025774
David Harel, Orna Kupferman, Moshe Y. Vardi, On the Complexity of Verifying Concurrent Transition Systems international conference on concurrency theory. pp. 258- 272 ,(1997) , 10.1007/3-540-63141-0_18
Rajeev Motwani, John E. Hopcroft, Jeffrey D. Ullman, Rotwani, Introduction to Automata Theory, Languages, and Computation ,(1979)
Moshe Y Vardi, Pierre Wolper, An Automata-Theoretic Approach to Automatic Program Verification IEEE Computer Society. ,(1986)
David Harel, Statecharts: A visual formalism for complex systems Science of Computer Programming. ,vol. 8, pp. 231- 274 ,(1987) , 10.1016/0167-6423(87)90035-9
Doron Drusinsky, David Harel, On the power of bounded concurrency I Journal of the ACM. ,vol. 41, pp. 517- 539 ,(1994) , 10.1145/176584.176587
G.J. Holzmann, The model checker SPIN formal methods in software practice. ,vol. 23, pp. 279- 295 ,(1997) , 10.1109/32.588521
Grady Booch, James Rumbaugh, Ivar Jacobson, The Unified Modeling Language User Guide ,(1999)