Testing membership for timed automata

DOI10.1007/S00236-023-00442-8arXiv1912.08277OpenAlexW2994801311MaRDI QIDQ6090987FDOQ6090987

Authors: Richard Lassaigne, Michel de Rougemont 

Publication date: 21 November 2023

Published in: Acta Informatica (Search for Journal in Brave)

Abstract: Given a timed automata which admits thick components and a timed word $x$, we present a tester which decides if $x$ is in the language of the automaton or if $x$ is $epsilon$-far from the language, using finitely many samples taken from the weighted time distribution $mu$ associated with an input $x$. We introduce a distance between timed words, the {em timed edit distance}, which generalizes the classical edit distance. A timed word $x$ is $epsilon$-far from a timed language if its relative distance to the language is greater than $epsilon$.

Full work available at URL: https://arxiv.org/abs/1912.08277

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• A theory of timed automata
• Property testing of regular tree languages
• Approximate satisfiability and equivalence
• Property testing and its connection to learning and approximation
• Random sampling with a reservoir
• Probabilistic checking of proofs
• Formal Methods for the Design of Real-Time Systems
• On Context-Free Languages
• EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
• Self-testing/correcting with applications to numerical problems
• The String-to-String Correction Problem
• Robust Characterizations of Polynomials with Applications to Program Testing
• Designing programs that check their work
• Title not available (Why is that?)
• Robust safety of timed automata
• Regular languages are testable with a constant number of queries
• Robust reachability in timed automata: a game-based approach
• Dynamical properties of timed automata
• Factorization forests of finite height
• Entropy of regular timed languages
• Distance on timed words and applications
• Edit distance for timed automata

Cited In (1)

• Testing membership in parenthesis languages

This page was built for publication: Testing membership for timed automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6090987)