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$.
翻译：给定一个支持厚组件的定时自动机和一个定时词$x$，我们提出了一个测试器，使用从与输入$x$关联的加权时间分布$\mu$中取出的有限个样本来决定$x$是否属于自动机的语言，或者$x$是否与该语言$\epsilon$-远。 我们介绍了一种定时单词之间的距离——“定时编辑距离”，它是经典编辑距离的推广。如果一个定时单词$x$到某个定时语言的相对距离大于$\epsilon$，那么$x$从这个定时语言中$\epsilon$-远。
相关内容
微信扫码咨询专知VIP会员