NDLI: Edit distance for timed automata

Please wait, while we are loading the content...

Computation of piecewise affine terminal cost functions for model predictive control

A type-based analysis of causality loops in hybrid systems modelers

Stability analysis of large-scale networked control systems with local networks: a hybrid small-gain approach

Cells driven by computers: long-term model predictive control of gene expression in yeast

Component based design of hybrid systems: a case study on concurrency and coupling

Inner approximated reachability analysis

On approximation metrics for linear temporal model-checking of stochastic systems

Parameter synthesis for polynomial biological models

Temporal logic inference for classification and prediction from data

Stabilizing discrete-time switched linear systems

Stochastic reachability based motion planning for multiple moving obstacle avoidance

A hyperdense semantic domain for hybrid dynamic systems to model different classes of discontinuities

Model reduction of switched affine systems: a method based on balanced truncation and randomized optimization

JSR: a toolbox to compute the joint spectral radius

Sampling-based approximation of the viability kernel for high-dimensional linear sampled-data systems

Resilience to intermittent assumption violations in reactive synthesis

Compositionality results for cardiac cell dynamics

Energy and mean-payoff timed games

An LQ sub-optimal stabilizing feedback law for switched linear systems

Timely monitoring of partially observable stochastic systems

Quasi-dependent variables in hybrid automata

Control to facet for polynomial systems

A bounded model checking tool for periodic sample-hold systems

Proofs from simulations and modular annotations

Model measuring for hybrid systems

Powertrain control verification benchmark

Abstraction, discretization, and robustness in temporal logic control of dynamical systems

State-feedback stabilization of discrete-time piecewise affine systems

Simulation-guided lyapunov analysis for hybrid dynamical systems

Abstracting and refining robustness for cyber-physical systems

Dynamic multi-domain bipedal walking with atrias through SLIP based human-inspired control

Edit distance for timed automata

Content Provider	ACM Digital Library
Author	Ibsen-Jensen, Rasmus Majumdar, Rupak Chatterjee, Krishnendu
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.
Starting Page	303
Ending Page	312
Page Count	10
File Format	PDF
ISBN	9781450327329
DOI	10.1145/2562059.2562141
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-04-15
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Edit distance Rectangular hybrid automata Timed automata
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Implementing real-time transactional security property using timed edit automata

Model Checking Rectangular Hybrid Systems with Timed Computation Tree Logic

Hybrid automata-based cegar for rectangular hybrid automata

1An Edit-distance Model for the Approximate Matching of Timed Strings

Timed control for rectangular hybrid systems

Cellular automata and substitutions in the edit-distance space

Timed control for rectangular hybrid systems (2012)

Edit-distance of weighted automata

Timed control for rectangular hybrid systems

Edit distance for timed automata

Similar Documents

Implementing real-time transactional security property using timed edit automata

Model Checking Rectangular Hybrid Systems with Timed Computation Tree Logic

Hybrid automata-based cegar for rectangular hybrid automata

1An Edit-distance Model for the Approximate Matching of Timed Strings

Timed control for rectangular hybrid systems

Cellular automata and substitutions in the edit-distance space

Timed control for rectangular hybrid systems (2012)

Edit-distance of weighted automata

Timed control for rectangular hybrid systems

Edit distance for timed automata