دانلود کتاب Computer Science - Theory and Applications: Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings

فهرست مطالب :

Front Matter....Pages -
Well-Founded and Partial Stable Semantics Logical Aspects....Pages 1-11
The Reachability Problem over Infinite Graphs....Pages 12-18
Kolmogorov Complexity and Model Selection....Pages 19-24
Automatic Verification of Heap-Manipulating Programs Using Separation Logic....Pages 25-25
Canonical Calculi: Invertibility, Axiom Expansion and (Non)-determinism....Pages 26-37
Integrality Property in Preemptive Parallel Machine Scheduling....Pages 38-46
Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes....Pages 47-58
k -SAT Is No Harder Than Decision-Unique- k -SAT....Pages 59-70
Unique Decipherability in the Monoid of Languages: An Application of Rational Relations....Pages 71-79
Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model....Pages 80-91
Approximability Distance in the Space of H -Colourability Problems....Pages 92-104
On Random Ordering Constraints....Pages 105-116
Depth Reduction for Circuits with a Single Layer of Modular Counting Gates....Pages 117-128
A Feebly Secure Trapdoor Function....Pages 129-142
Partitioning Graphs into Connected Parts....Pages 143-154
Structural Complexity of AvgBPP....Pages 155-166
Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials....Pages 167-178
Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity....Pages 179-190
One-Nonterminal Conjunctive Grammars over a Unary Alphabet....Pages 191-202
Concatenation of Regular Languages and Descriptional Complexity....Pages 203-214
Approximability of the Maximum Solution Problem for Certain Families of Algebras....Pages 215-226
Complete Complexity Classification of Short Shop Scheduling....Pages 227-236
Compressed Word Problems in HNN-Extensions and Amalgamated Products....Pages 237-249
Variations on Muchnik’s Conditional Complexity Theorem....Pages 250-262
An Optimal Bloom Filter Replacement Based on Matrix Solving....Pages 263-273
Aperiodicity Measure for Infinite Sequences....Pages 274-285
On the Complexity of Matroid Isomorphism Problems....Pages 286-298
Breaking Anonymity by Learning a Unique Minimum Hitting Set....Pages 299-309
The Budgeted Unique Coverage Problem and Color-Coding....Pages 310-321
Formal Verification of Gate-Level Computer Systems....Pages 322-333
On Models of a Nondeterministic Computation....Pages 334-345
New Plain-Exponential Time Classes for Graph Homomorphism....Pages 346-355
Languages Recognized with Unbounded Error by Quantum Finite Automata....Pages 356-367
Back Matter....Pages -