一句话：为跳跃自动机提出四种基于跳转代价的定量语义，并确定其有界性问题的可判定性与复杂度。
跳跃自动机允许读头在输入单词的各个位置间“跳跃”，以非顺序方式读取输入。本文主张读头的跳跃应当产生代价，并据此提出四种定量语义：绝对距离语义统计读头跳过的总距离，反转语义统计读头改变方向的次数，Hamming距离语义度量运行中交换字母的次数，最大跳跃语义则统计单步中的最大跳距。接受运行的代价由这些跳转相关的量定义。作者重点研究有界性问题：给定一个跳跃自动机，判定其定量语言是否被某个给定数k所界定。论文针对多种变体建立了该问题的可判定性，并给出了相应的复杂度结果。
Jumping automata are finite automata that read their input in a non-sequential manner, by allowing a reading head to ``jump'' between positions on the input, consuming a permutation of the input word. We argue that allowing the head to jump should incur some cost. To this end, we propose four quantitative semantics for jumping automata, whereby the jumps of the head in an accepting run define the cost of the run. The four semantics correspond to different interpretations of jumps: the \emph{absolute distance} semantics counts the distance the head jumps, the \emph{reversal} semantics counts the number of times the head changes direction, the \emph{Hamming distance} measures the number of letter-swaps the run makes, and the \emph{maximum jump} semantics counts the maximal distance the head jumps in a single step, We study these measures, with the main focus being the \emph{boundedness problem}: given a jumping automaton, decide whether its (quantitative) language is bounded by some given number $k$. We establish the decidability and complexity for this problem under several variants.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{AlmagorDS25,
title = {Quantitative Semantics for Jumping Automata},
author = {Shaull Almagor and Neta Dafni and Ishai Salgado},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 4},
year = {2025},
doi = {10.46298/lmcs-21(4:31)2025}
}