Abstract
A well-established theory exists for testing finite state machines. One fundamental class of problems handled by this theory is state identification: we are given a machine with known state space and transition relation, but unknown initial state, and we are asked to find tests which identify the initial or final state of the machine. In this paper, we study state identification in the context of timed automata which contrary to, say, Mealy or Moore machines, is a suitable model for real-time systems. We are interested in digital-clock tests which have a finite clock precision and are thus implementable. We develop a general technique, based on time-abstracting bisimulation, which reduces the problem to the case of non-deterministic finite-state Mealy machines. We illustrate our technique on a toy example.
Work partially supported by CNRS STIC project “CORTOS” and by IST Network of Excellence “ARTIST2”.
Chapter PDF
Similar content being viewed by others
References
Alur, R., Courcoubetis, C., Yannakakis, M.: Distinguishing tests for nondeterministic and probabilistic machines. In: 27th ACM Symposium on Theory of Computing (STOC 1995), pp. 363–372 (1995)
Alur, R., Dill, D.: A theory of timed automata. Theoretical Computer Science 126, 183–235 (1994)
Bornot, S., Sifakis, J., Tripakis, S.: Modeling urgency in timed systems. In: de Roever, W.-P., Langmaack, H., Pnueli, A. (eds.) COMPOS 1997. LNCS, vol. 1536, p. 103. Springer, Heidelberg (1998)
Daws, C., Olivero, A., Tripakis, S., Yovine, S.: The tool Kronos. In: Alur, R., Sontag, E.D., Henzinger, T.A. (eds.) HS 1995. LNCS, vol. 1066, pp. 208–219. Springer, Heidelberg (1996)
Gill, A.: State-identification experiments in finite automata. Information and Control 4, 132–154 (1961)
Grinchtein, O., Jonsson, B., Leucker, M.: Learning of event-recording automata. In: Lakhnech, Y., Yovine, S. (eds.) FORMATS 2004 and FTRTFT 2004. LNCS, vol. 3253, pp. 379–395. Springer, Heidelberg (2004)
Krichen, M., Tripakis, S.: Black-box conformance testing for real-time systems. In: Graf, S., Mounier, L. (eds.) SPIN 2004. LNCS, vol. 2989, pp. 109–126. Springer, Heidelberg (2004)
Lee, D., Yannakakis, M.: Principles and methods of testing finite state machines - A survey. Proceedings of the IEEE 84, 1090–1126 (1996)
Moore, E.F.: Gedanken-experiments on sequential machines. In: Automata Studies, vol. 34. Princeton University Press, Princeton (1956)
Sifakis, J., Yovine, S.: Compositional specification of timed systems. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046. Springer, Heidelberg (1996)
Tripakis, S., Yovine, S.: Analysis of timed systems using time-abstracting bisimulations. Formal Methods in System Design 18(1), 25–68 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 IFIP International Federation for Information Processing
About this paper
Cite this paper
Krichen, M., Tripakis, S. (2005). State Identification Problems for Timed Automata. In: Khendek, F., Dssouli, R. (eds) Testing of Communicating Systems. TestCom 2005. Lecture Notes in Computer Science, vol 3502. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11430230_13
Download citation
DOI: https://doi.org/10.1007/11430230_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26054-7
Online ISBN: 978-3-540-32076-0
eBook Packages: Computer ScienceComputer Science (R0)