Titlebook: Automata, Languages and Programming; 31st International C Josep Díaz,Juhani Karhumäki,Donald Sannella Conference proceedings 2004 Springer-

废除

LINES

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

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.

破译密码

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

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

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

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.