废除
发表于 2025-4-1 02:38:12
http://reply.papertrans.cn/17/1663/166215/166215_61.png
LINES
发表于 2025-4-1 07:27:31
Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Inputroblems. The grammar compression is more convenient than .-encoding, its size differs from that of .-encoding by at most logarithmic factor, the constructive proof is based on the concept similar to balanced trees.
Abbreviate
发表于 2025-4-1 11:53:43
Deciding Knowledge in Security Protocols Under Equational Theorieslations. The messages in question may employ functions (encryption, decryption, etc.) axiomatized in an equational theory. Our main positive results say that, for a large and useful class of equational theories, deducibility and indistinguishability are both decidable in polynomial time.
破译密码
发表于 2025-4-1 16:55:26
Representing Nested Inductive Types Using W-Types a result by Dybjer (1997) who showed that non-nested strictly positive inductive types can be represented using W-types. We also provide a detailed analysis of the categorical infrastructure needed to establish the result.
VOC
发表于 2025-4-1 18:40:40
Learning a Hidden Subgraphetting, we prove nearly matching upper and lower bounds for the minimum possible number of queries required when the family is the family of all stars of a given size or all cliques of a given size. We further describe some bounds that apply to general graphs.
PHIL
发表于 2025-4-2 00:57:07
Optimal Reachability for Weighted Timed Gamesnly known complexity bound for this problem is a doubly-exponential upper bound. We establish a singly-exponential upper bound and show that there exist automata with exponentially many states in a single region with pair-wise distinct optimal strategies.
CANON
发表于 2025-4-2 05:10:05
External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphsith just . I/Os. Both our weighted and unweighted approaches require .(..) space. For diameter computations we provide I/O-space tradeoffs. Finally, we provide improved results for both diameter and APSP computation on directed planar graphs.