research-article

Edit distance for timed automata

Authors:

Krishnendu Chatterjee,

Rasmus Ibsen-Jensen,

Rupak MajumdarAuthors Info & Claims

HSCC '14: Proceedings of the 17th international conference on Hybrid systems: computation and control

Pages 303 - 312

https://doi.org/10.1145/2562059.2562141

Published: 15 April 2014 Publication History

Abstract

The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition.

In this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in time stamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than δ away from the parameter, for δ < 0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and analogous decidability results hold for rectangular automata.

References

[1]

A. Aho and T. Peterson. A minimum distance error-correcting parser for context-free languages. SIAM J. of Computing, 1:305--312, 1972.

[2]

R. Alur and D. L. Dill. A theory of timed automata. Theoretical Computer Science, 126:183--235, 1994.

Digital Library

[3]

M. Benedikt, G. Puppis, and C. Riveros. Regular repair of specifications. In LICS, pages 335--344. IEEE Computer Society, 2011.

Digital Library

[4]

R. Brenguier, S. Göoller, and O. Sankur. A comparison of succinctly represented finite-state systems. In CONCUR, pages 147--161, 2012.

Digital Library

[5]

K. Chatterjee and V. S. Prabhu. Quantitative timed simulation functions and refinement metrics for real-time systems. In HSCC, 2013.

Digital Library

[6]

A. Donzé, T. Ferrère, and O. Maler. Efficient robust monitoring of signal temporal logic. In CAV 2013, LNCS. Springer, 2013.

Digital Library

[7]

A. Donzé and O. Maler. Robust satisfaction of temporal logic over real-valued signals. In FORMATS, LNCS, pages 92--106. Springer, 2010.

Digital Library

[8]

G. Fainekos and G. Pappas. Robustness of temporal logic specifications for continuous-time signals. Theoretical Computer Science, 410(42), 2009.

Digital Library

[9]

G. Fainekos, S. Sankaranarayanan, K. Ueda, and H. Yazarel. Verification of automotive control applications using S-TaLiRo. In Proc. American Control Conference, 2012.

[10]

T. A. Henzinger and P. W. Kopke. Discrete-time control for rectangular hybrid automata. Theor. Comput. Sci., 221(1--2):369--392, June 1999.

Digital Library

[11]

J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Adison-Wesley Publishing Company, Reading, Massachusets, USA, 1979.

Digital Library

[12]

R. Karp. Mapping the genome: some combinatorial problems arising in molecular biology. In STOC 93, pages 278--285. ACM, 1993.

Digital Library

[13]

V. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics-Doklady, 10:707--710, 1966.

[14]

M. Mohri. Edit-distance of weighted automata: general definitions and algorithms. Intl. J. of Foundations of Comp. Sci., 14:957--982, 2003.

[15]

T. Okuda, E. Tanaka, and T. Kasai. A method for the correction of garbled words based on the levenshtein metric. IEEE Trans. Comput., 25:172--178, 1976.

Digital Library

[16]

J. Ouaknine and J. Worrell. Universality and language inclusion for open and closed timed automata. In O. Maler and A. Pnueli, editors, HSCC, volume 2623 of Lecture Notes in Computer Science, pages 375--388. Springer, 2003.

Digital Library

[17]

G. Pighizzini. How hard is computing the edit distance? Information and Computation, 165:1--13, 2001.

Digital Library

[18]

W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4(2):177--192, Apr. 1970.

Digital Library

[19]

R. A. Wagner. Order-n correction for regular languages. Commun. ACM, 17(5):265--268, 1974.

Digital Library

[20]

R. A. Wagner and M. J. Fischer. The string-to-string correction problem. J. ACM, 21(1):168--173, Jan. 1974.

Digital Library

Cited By

Rino NChatain T(2024)Timed Alignments with Mixed MovesBusiness Process Management Workshops10.1007/978-3-031-50974-2_15(186-197)Online publication date: 11-Jan-2024
https://doi.org/10.1007/978-3-031-50974-2_15
Lassaigne Rde Rougemont M(2023)Testing membership for timed automataActa Informatica10.1007/s00236-023-00442-860:4(361-384)Online publication date: 17-Jul-2023
https://doi.org/10.1007/s00236-023-00442-8
Wang SMa J(2022)NMT Sentence Granularity Similarity Calculation Method Based on Improved Cosine DistanceProceedings of the 2022 5th International Conference on Artificial Intelligence and Pattern Recognition10.1145/3573942.3574021(270-276)Online publication date: 23-Sep-2022
https://dl.acm.org/doi/10.1145/3573942.3574021
Show More Cited By

Index Terms

Edit distance for timed automata
1. Theory of computation
  1. Models of computation
    1. Computability

Recommendations

Edit distance neighbourhoods of input-driven pushdown automata
Abstract
Edit distance ℓ-neighbourhood of a formal language is the set of all strings that can be transformed to one of the strings in this language by at most ℓ insertions and deletions. Both the regular and the context-free languages are ...
Input-driven pushdown automata for edit distance neighborhood
Abstract
Edit distance ℓ-neighborhood of a language L is the set of all strings that can be obtained by at most ℓ elementary edit operations — deleting or inserting one symbol in the string — from some string in L. We shall show that if L is ...
Computing the edit distance of a regular language

The edit distance (or Levenshtein distance) between two words is the smallest number of substitutions, insertions, and deletions of symbols that can be used to transform one of the words into the other. In this paper, we consider the problem of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HSCC '14: Proceedings of the 17th international conference on Hybrid systems: computation and control

April 2014

328 pages

ISBN:9781450327329

DOI:10.1145/2562059

Program Chairs:
Martin Fráänzle
Carl von Ossietziky Universität Oldenburg, Germany
,
John Lygeros
ETH Zurich, Switzerland

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 April 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

HSCC'14

Sponsor:

SIGBED

HSCC'14: 17th International Conference on Hybrid Systems: Computation and Control

April 15 - 17, 2014

Berlin, Germany

Acceptance Rates

HSCC '14 Paper Acceptance Rate 29 of 69 submissions, 42%;

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
165
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rino NChatain T(2024)Timed Alignments with Mixed MovesBusiness Process Management Workshops10.1007/978-3-031-50974-2_15(186-197)Online publication date: 11-Jan-2024
https://doi.org/10.1007/978-3-031-50974-2_15
Lassaigne Rde Rougemont M(2023)Testing membership for timed automataActa Informatica10.1007/s00236-023-00442-860:4(361-384)Online publication date: 17-Jul-2023
https://doi.org/10.1007/s00236-023-00442-8
Wang SMa J(2022)NMT Sentence Granularity Similarity Calculation Method Based on Improved Cosine DistanceProceedings of the 2022 5th International Conference on Artificial Intelligence and Pattern Recognition10.1145/3573942.3574021(270-276)Online publication date: 23-Sep-2022
https://dl.acm.org/doi/10.1145/3573942.3574021
Paik YKim SJung DKim M(2020)Generating Representative Test Sequences from Real Workload for Minimizing DRAM Verification OverheadACM Transactions on Design Automation of Electronic Systems10.1145/339189125:4(1-23)Online publication date: 27-May-2020
https://dl.acm.org/doi/10.1145/3391891
Lanotte RTini S(2019)Computing Bisimilarity Metrics for Probabilistic Timed AutomataIntegrated Formal Methods10.1007/978-3-030-34968-4_17(303-321)Online publication date: 22-Nov-2019
https://doi.org/10.1007/978-3-030-34968-4_17
Asarin EBasset NDegorre A(2018)Distance on Timed Words and ApplicationsFormal Modeling and Analysis of Timed Systems10.1007/978-3-030-00151-3_12(199-214)Online publication date: 26-Aug-2018
https://doi.org/10.1007/978-3-030-00151-3_12
Majumdar RPrabhu VGirard ASankaranarayanan S(2015)Computing the Skorokhod distance between polygonal tracesProceedings of the 18th International Conference on Hybrid Systems: Computation and Control10.1145/2728606.2728618(199-208)Online publication date: 14-Apr-2015
https://dl.acm.org/doi/10.1145/2728606.2728618
Chatterjee KHenzinger TIbsen-Jensen ROtop J(2015)Edit Distance for Pushdown AutomataProceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming - Volume 913510.1007/978-3-662-47666-6_10(121-133)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-662-47666-6_10

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents