Edit Distance for Timed Automata

Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Majumdar, Rupak (2013) Edit Distance for Timed Automata. Technical Report. IST Austria.

[img] Text
main.pdf - Published Version
Available under License All rights reserved.
[IST-2013-144-v1+1]
Download (202Kb)
Official URL: http://dx.doi.org/10.1145/2562059.2562141

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 timestamps. 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 $\delta$ away from the parameter, for $\delta>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 we show analogous decidability results for rectangular automata.

Item Type: Monograph (Technical Report)
Uncontrolled Keywords: A short version of this technical report is available at http://dx.doi.org/10.1145/2562059.2562141
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
Research Group: Chatterjee Group
Depositing User: Prof Krishnendu Chatterjee
Date Deposited: 30 Oct 2013 10:18
Last Modified: 20 Jul 2019 12:49
URI: https://repository.ist.ac.at/id/eprint/144

Actions (login required)

View Item View Item