Abstract
Each timed process exhibits a kind of input-output behaviour when subjected to asynchronous testing. This behaviour is called the asynchronous test behaviour of the process. Two processes exhibiting the same asynchronous test behaviour are called asynchronous test equivalent. In this paper, we first formalize the notion of asynchronous test behaviour of a timed process, and then address the following decision problem. Given two timed processes, determine whether they are asynchronous test equivalent or not. We prove this problem to be undecidable. The undecidability result holds even for processes with one clock.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Alur, R., Dill, D.L.: A theory of timed automata. Theor. Comput. Sci. 126, 183–235 (1994)
Alur, R., Madhusudan, P.: Decision problems for timed automata: a survey. In: International School on Formal Methods for the Design of Computer, Communication and Software Systems, SFM-RT 2004, Bertinoro, Italy, 13–18 September 2004, pp. 1–24 (2004)
Bhateja, P.: Asynchronous test equivalence over probabilistic processes. In: 27th Asia-Pacific Software Engineering Conference, APSEC-2020, Singapore, 1–4 December 2020
Bhateja, P.: Determining asynchronous test equivalence for probabilistic processes. Inf. Process. Lett. 177, 106269 (2022)
Bhateja, P., Gastin, P., Mukund, M.: A fresh look at testing for asynchronous communication. In: Graf, S., Zhang, W. (eds.) ATVA 2006. LNCS, vol. 4218, pp. 369–383. Springer, Heidelberg (2006). https://doi.org/10.1007/11901914_28
Boreale, M., De Nicola, R., Pugliese, R.: Trace and testing equivalence on asynchronous processes. Inf. Comput. 172, 139–164 (2002)
Castellani, I., Hennessy, M.: Testing theories for asynchronous languages. In: Arvind, V., Ramanujam, S. (eds.) FSTTCS 1998. LNCS, vol. 1530, pp. 90–101. Springer, Heidelberg (1998). https://doi.org/10.1007/978-3-540-49382-2_9
De Nicola, R., Hennessy, M.: Testing equivalences for processes. Theor. Comput. Sci. 34, 83–133 (1984)
Henzinger, T., Nicollin, X., Sifakis, J., Yovine, S.: Symbolic model checking for real-time systems. Inf. Comput. 111(2), 193–244 (1994)
Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Adison-Wesley Publishing Company, Reading (1979)
Keller, R.M.: Formal verification of parallel programs. Commun. ACM 19, 371–384 (1976)
Laroussinie, F., Markey, N., Schnoebelen, P.: Model checking timed automata with one or two clocks. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 387–401. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28644-8_25
Ouaknine, J., Worrell, J.: On the language inclusion problem for timed automata: closing a decidability gap. In: Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, pp. 54–63 (2004)
van Glabbeek, R.J.: The linear time - branching time spectrum I. In: Bergstra, J.A., Ponse, A., Smolka, S.A. (eds.) Handbook of Process Algebra, pp. 3–99. North-Holland/Elsevier (2001)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bhateja, P. (2023). Asynchronous Test Equivalence over Timed Processes. In: David, C., Sun, M. (eds) Theoretical Aspects of Software Engineering. TASE 2023. Lecture Notes in Computer Science, vol 13931. Springer, Cham. https://doi.org/10.1007/978-3-031-35257-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-35257-7_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-35256-0
Online ISBN: 978-3-031-35257-7
eBook Packages: Computer ScienceComputer Science (R0)