Testing membership for timed automata

DOI10.1007/S00236-023-00442-8MaRDI QIDQ6090987zbMATH OpenOpenAlexFDO

Authors Richard Lassaigne, Michel de Rougemont

Publication date 21 November 2023

Published in Acta Informatica (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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$.

Recommendations

• On the distance between timed automata
• A theory of timed automata
• Edit distance for timed automata
• Dynamic data structures for timed automata acceptance
• Testing timed automata

Cites work

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

Cited in

(3)

• Dynamic data structures for timed automata acceptance
• Dynamic data structures for timed automata acceptance
• 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)