research-article

The efficiency of identifying timed automata and the power of clocks

Authors:

Mathijs de Weerdt,

Cees WitteveenAuthors Info & Claims

Information and Computation, Volume 209, Issue 3

Pages 606 - 625

https://doi.org/10.1016/j.ic.2010.11.023

Published: 01 March 2011 Publication History

Abstract

We develop theory on the efficiency of identifying (learning) timed automata. In particular, we show that: (i) deterministic timed automata cannot be identified efficiently in the limit from labeled data and (ii) that one-clock deterministic timed automata can be identified efficiently in the limit from labeled data. We prove these results based on the distinguishability of these classes of timed automata. More specifically, we prove that the languages of deterministic timed automata cannot, and that one-clock deterministic timed automata can be distinguished from each other using strings in length bounded by a polynomial. In addition, we provide an algorithm that identifies one-clock deterministic timed automata efficiently from labeled data.Our results have interesting consequences for the power of clocks that are interesting also out of the scope of the identification problem.

References

[1]

Alur, R. and Dill, D.L., A theory of timed automata. Theoret. Comput. Sci. v126 i2. 183-235.

Digital Library

[2]

Larsen, K.G., Petterson, P. and Yi, W., Uppaal in a nutschell. Int. J. Software Tools Technol. Transfer. v1 i1--2. 134-152.

[3]

Sipser, M., Introduction to the Theory of Computation. 1997. PWS Publishing.

Digital Library

[4]

L.R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, in: Proceedings of the IEEE, vol. 77, 1989, pp. 267--296.

Digital Library

[5]

S. Verwer, M. de Weerdt, C. Witteveen, An algorithm for learning real-time automata, in: M. van Someren, S. Katrenko, P. Adriaans (Eds.), Proceedings of the Sixteenth Annual Machine Learning Conference of Belgium and The Netherlands, 2007, pp. 128--135.

[6]

Lang, K.J., Pearlmutter, B.A. and Price, R.A., Results of the Abbadingo one DFA learning competition and a new evidence-driven state merging algorithm. In: LNCS, vol. 1433. Springer.

Digital Library

[7]

Alur, R., Fix, L. and Henzinger, T.A., Event-clock automata: a determinizable class of timed automata. Theoret. Comput. Sci. v211 i1. 253-273.

Digital Library

[8]

Grinchtein, O., Jonsson, B. and Petterson, P., Inference of event-recording automata using timed decision trees. In: LNCS, vol. 4137. Springer. pp. 435-449.

Digital Library

[9]

Gold, E.M., Complexity of automaton identification from given data. Inform. and Control. v37 i3. 302-320.

[10]

Pitt, L. and Warmuth, M., The minimum consistent DFA problem cannot be approximated within and polynomial. In: Annual ACM Symposium on Theory of Computing, ACM. pp. 421-432.

Digital Library

[11]

Gold, E.M., Language identification in the limit. Inform. and Control. v10 i5. 447-474.

[12]

de la Higuera, C., Characteristic sets for polynomial grammatical inference. Mach. Learn. v27 i2. 125-138.

Digital Library

[13]

Oncina, J. and Garcia, P., Inferring regular languages in polynomial update time. In: Series in Machine Perception and Artificial Intelligence, vol. 1. World Scientific. pp. 49-61.

[14]

Yokomori, T., On polynomial-time learnability in the limit of strictly deterministic automata. Mach. Learn. v19 i2. 153-179.

Digital Library

[15]

Laroussinie, F., Markey, N. and Schnoebelen, P., Model checking timed automata with one or two clocks. In: LNCS, vol. 3170. Springer. pp. 387-401.

Digital Library

[16]

Asarin, E., Caspi, P. and Maler, O., Timed regular expressions. J. Assoc. Comput. Mach. v49 i2. 172-206.

Digital Library

[17]

Yokomori, T., Learning non-deterministic finite automata from queries and counterexamples. 1993. Machine Intelligence, 1993.Oxford University Press.

[18]

Goldman, S.A. and Mathias, H.D., Teaching a smarter learner. J. Comput. Syst. Sci. v52 i2. 255-267.

Digital Library

[19]

Jiang, T. and Ravikumar, B., Minimal NFA problems are hard. SIAM J. Comput. v22. 1117-1141.

Digital Library

[20]

Dietterich, T.G., Ensemble methods in machine learning. In: LNCS, vol. 1857. Springer. pp. 1-15.

Digital Library

[21]

Jain, S., Osherson, D., Royer, J.S. and Sharma, A., Systems that Learn. 1999. MIT Press.

Cited By

Teng YZhang MAn J(2024)Learning Deterministic Multi-Clock Timed AutomataProceedings of the 27th ACM International Conference on Hybrid Systems: Computation and Control10.1145/3641513.3650124(1-11)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3641513.3650124
Xu RAn JZhan B(2022)Active Learning of One-Clock Timed Automata Using Constraint SolvingAutomated Technology for Verification and Analysis10.1007/978-3-031-19992-9_16(249-265)Online publication date: 25-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-19992-9_16
An JZhan BZhan NZhang M(2021)Learning Nondeterministic Real-Time AutomataACM Transactions on Embedded Computing Systems10.1145/347703020:5s(1-26)Online publication date: 31-Oct-2021
https://dl.acm.org/doi/10.1145/3477030
Show More Cited By

The efficiency of identifying timed automata and the power of clocks
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Interrupt Timed Automata: verification and expressiveness

We introduce the class of Interrupt Timed Automata (ITA), a subclass of hybrid automata well suited to the description of timed multi-task systems with interruptions in a single processor environment.

While the reachability problem is undecidable for ...
Efficiently identifying deterministic real-time automata from labeled data

We develop a novel learning algorithm RTI for identifying a deterministic real-time automaton (DRTA) from labeled time-stamped event sequences. The RTI algorithm is based on the current state of the art in deterministic finite-state automaton (DFA) ...
Alternating timed automata

A notion of alternating timed automata is proposed. It is shown that such automata with only one clock have decidable emptiness problem over finite words. This gives a new class of timed languages that is closed under boolean operations and which has an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 209, Issue 3

March, 2011

378 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 March 2011

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Teng YZhang MAn J(2024)Learning Deterministic Multi-Clock Timed AutomataProceedings of the 27th ACM International Conference on Hybrid Systems: Computation and Control10.1145/3641513.3650124(1-11)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3641513.3650124
Xu RAn JZhan B(2022)Active Learning of One-Clock Timed Automata Using Constraint SolvingAutomated Technology for Verification and Analysis10.1007/978-3-031-19992-9_16(249-265)Online publication date: 25-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-19992-9_16
An JZhan BZhan NZhang M(2021)Learning Nondeterministic Real-Time AutomataACM Transactions on Embedded Computing Systems10.1145/347703020:5s(1-26)Online publication date: 31-Oct-2021
https://dl.acm.org/doi/10.1145/3477030
Bresolin DEl-Fakih KVilla TYevtushenko N(2021)Equivalence checking and intersection of deterministic timed finite state machinesFormal Methods in System Design10.1007/s10703-022-00396-659:1-3(77-102)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s10703-022-00396-6
Jin XAn JZhan BZhan NZhang M(2021)Inferring Switched Nonlinear Dynamical SystemsFormal Aspects of Computing10.1007/s00165-021-00542-733:3(385-406)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s00165-021-00542-7
Shen WAn JZhan BZhang MXue BZhan N(2020)PAC Learning of Deterministic One-Clock Timed AutomataFormal Methods and Software Engineering10.1007/978-3-030-63406-3_8(129-146)Online publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1007/978-3-030-63406-3_8

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents