Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Độ tương đương kiểm thử như một độ tương đương bisimulation
Tóm tắt
Trong bài báo này, chúng tôi chỉ ra cách mà độ tương đương kiểm thử và thứ tự tiền đề trên các hệ thống chuyển tiếp có thể được diễn giải như các trường hợp của độ tương đương bisimulation tổng quát và thứ tự tiền bisimulation. Việc đặc trưng hóa dựa trên việc định nghĩa các phép biến đổi trên các hệ thống chuyển tiếp sao cho các quan hệ kiểm thử trên các hệ thống gốc tương ứng với các quan hệ (tiền) bisimulation trên các hệ thống đã biến đổi. Dựa trên những kết quả này, có thể sử dụng các thuật toán để xác định các quan hệ (tiền) bisimulation trong trường hợp các hệ thống chuyển tiếp trạng thái hữu hạn để tính toán các quan hệ kiểm thử.
Từ khóa
#độ tương đương kiểm thử #bisimulation #tiền bisimulation #hệ thống chuyển tiếp #quan hệ kiểm thửTài liệu tham khảo
Bloom, B., Istrail, S., and Meyer, A. “Bisimulation Can't Be Traced.”Proceedings of the ACM Symposium on Principles of Programming Languages, 1988.
Cleaveland, R., Parrow, J., and Steffen, B. “The Concurrency Workbench.” InProceedings of the Workshop on Automatic Verification Methods for Finite-State Systems, pp. 24–37.Lecture Notes in Computer Science 407. Springer-Verlag, Berlin, 1989.
Cleaveland, R., Parrow, J., and Steffen, B. “A Semantics-Based Verification Tool for Finite-State Systems.” InProceedings of the Ninth Annual Workshop on Protocol Specification, Testing and Verification, pp. 287–302. North-Holland, Amsterdam, 1990.
Cleaveland, R., Parrow, J., and Steffen, B. “The Concurrency Workbench: A Semantics-Based Verification Tool for Finite-State Systems.” To appear inACM Transactions on Programming Languages and Systems.
DeNicola, R. and Hennessy, M. “Testing Equivalences for Processes.”Theoretical Computer Science 24, 1984, pp. 83–113.
Hennessy, M. “A Term Model for Synchronous Processes.”Information and Control, v. 51, n. 1, October 1981, pp. 58–75.
Hennessy, M. “Acceptance Trees.”Journal of the ACM, v. 32, n. 4, October 1985, pp. 896–928.
Hennessy, M.Algebraic Theory of Processes. MIT Press, Cambridge, 1988.
Hennessy, M. and Milner, R. “Algebraic Laws for Nondeterminism and Concurrency.”Journal of the ACM, v. 32, n. 1, January 1985, pp. 137–161.
Hoare, C.A.R.Communicating Sequential Processes. Prentice-Hall International, London, 1985.
Hopcroft, J. and Ullman, J.Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, 1979.
Kanellakis, P.C. and Smolka, S.A. “CCS Expressions, Finite State Processes, and Three Problems of Equivalence.”Information and Computation, v. 86, n. 1, May 1990, pp. 43–68.
Larsen, K. and Skou, A. “Bisimulation through Probabilistic Testing.”Proceedings of the ACM Symposium on Principles of Programming Languages, 1989.
Milner, R.A Calculus of Communicating Systems. Lecture Notes in Computer Science 92. Springer-Verlag, Berlin, 1980.
Milner, R. “Calculi for Synchrony and Asynchrony.”Theoretical Computer Science, v. 25, n. 3, July 1983, pp. 267–310.
Milner, R.Communication and Concurrency. Prentice-Hall, 1989.
Paige, R. and Tarjan, R.E. “Three Partition Refinement Algorithms.”SIAM Journal of Computing, v. 16, n. 6, December 1987, pp. 973–989.
Park, D. “Concurrency and Automata in Infinite Strings.”Lecture Notes in Computer Science 104, pp. 167–183. Springer-Verlag, Berlin, 1981.
Walker, D. “Bisimulations and Divergence in CCS.”Information and Computation 85, n. 2, pp. 202–241, 1990.