Mri485
发表于 2025-3-28 14:34:06
Input-Driven Pushdown Automata for Edit Distance Neighborhoodtates, which improves the known upper bound. We have obtained also a lower bound, namely, at least . states are required. If the measure of edit distance includes also the operation of rewriting one symbol with another, the edit distance .-neighborhood can be recognized with . pushdown symbols and . states.
贞洁
发表于 2025-3-28 21:45:56
Eventually Safe Languagesanguages. We introduce a class of properties called “eventually safe” together with a specification language . for this class. We finally give an algorithm to produce a Good-for-Games automaton from any . formula, thereby allowing synthesis for eventually safe properties.
DUCE
发表于 2025-3-28 23:58:23
http://reply.papertrans.cn/28/2703/270236/270236_43.png
ADORN
发表于 2025-3-29 03:29:02
Sachin A. Gupte,Michael S. Wolin in the deterministic setting it allows for exponential succinctness compared to the classic types, boolean operations on it only involve a quadratic size blowup, and its nonemptiness, universality, and containment checks are in PTIME.
hieroglyphic
发表于 2025-3-29 09:22:11
Inherent Size Blowup in ,-Automata in the deterministic setting it allows for exponential succinctness compared to the classic types, boolean operations on it only involve a quadratic size blowup, and its nonemptiness, universality, and containment checks are in PTIME.
饥荒
发表于 2025-3-29 12:20:26
http://reply.papertrans.cn/28/2703/270236/270236_46.png
不满分子
发表于 2025-3-29 16:23:55
http://reply.papertrans.cn/28/2703/270236/270236_47.png
凹处
发表于 2025-3-29 23:39:40
Characterizing the Valuedness of Two-Way Finite Transducersalued or not. As crossing sequences in two-way automata often play similar roles as states in their one-way counterparts, we derive in this paper analogous criteria in the setting of crossing sequences to characterize the infinite-valuedness of two-way finite transducers.
沉思的鱼
发表于 2025-3-30 03:09:20
http://reply.papertrans.cn/28/2703/270236/270236_49.png
Fracture
发表于 2025-3-30 06:48:19
Coinductive Algorithms for Büchi Automatan generates large and highly non-deterministic automata, we show how to exploit their specific structure and apply state-of-the art techniques based on coinduction to reduce the state-space that has to be explored. Doing so, we obtain algorithms which do not require full determinization or complementation.