LEADER 04224nam 2200601Ia 450 001 9910484414703321 005 20200520144314.0 010 $a1-280-38317-8 010 $a9786613561091 010 $a3-642-03351-2 024 7 $a10.1007/978-3-642-03351-3 035 $a(CKB)1000000000772858 035 $a(SSID)ssj0000316893 035 $a(PQKBManifestationID)11251766 035 $a(PQKBTitleCode)TC0000316893 035 $a(PQKBWorkID)10286410 035 $a(PQKB)10317651 035 $a(DE-He213)978-3-642-03351-3 035 $a(MiAaPQ)EBC3064435 035 $a(PPN)13995080X 035 $a(EXLCZ)991000000000772858 100 $a20090811d2009 uy 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aComputer science -- theory and applications $efourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009 : proceedings /$fAnna Frid ... [et al.] (eds.) 205 $a1st ed. 2009. 210 $aBerlin ;$aNew York $cSpringer$dc2009 215 $a1 online resource (XIII, 369 p.) 225 1 $aLecture notes in computer science,$x0302-9743 ;$v5675 225 1 $aLNCS sublibrary. SL 1, Theoretical computer science and general issues 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-642-03350-4 320 $aIncludes bibliographical references and index. 327 $aInvited Papers -- Well-Founded and Partial Stable Semantics Logical Aspects -- The Reachability Problem over Infinite Graphs -- Kolmogorov Complexity and Model Selection -- Automatic Verification of Heap-Manipulating Programs Using Separation Logic -- Accepted Papers -- Canonical Calculi: Invertibility, Axiom Expansion and (Non)-determinism -- Integrality Property in Preemptive Parallel Machine Scheduling -- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes -- k-SAT Is No Harder Than Decision-Unique-k-SAT -- Unique Decipherability in the Monoid of Languages: An Application of Rational Relations -- Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model -- Approximability Distance in the Space of H-Colourability Problems -- On Random Ordering Constraints -- Depth Reduction for Circuits with a Single Layer of Modular Counting Gates -- A Feebly Secure Trapdoor Function -- Partitioning Graphs into Connected Parts -- Structural Complexity of AvgBPP -- Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials -- Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity -- One-Nonterminal Conjunctive Grammars over a Unary Alphabet -- Concatenation of Regular Languages and Descriptional Complexity -- Approximability of the Maximum Solution Problem for Certain Families of Algebras -- Complete Complexity Classification of Short Shop Scheduling -- Compressed Word Problems in HNN-Extensions and Amalgamated Products -- Variations on Muchnik?s Conditional Complexity Theorem -- An Optimal Bloom Filter Replacement Based on Matrix Solving -- Aperiodicity Measure for Infinite Sequences -- On the Complexity of Matroid Isomorphism Problems -- Breaking Anonymity by Learning a Unique Minimum Hitting Set -- The Budgeted Unique Coverage Problem and Color-Coding -- Formal Verification of Gate-Level Computer Systems -- On Models of a Nondeterministic Computation -- New Plain-Exponential Time Classes for Graph Homomorphism -- Languages Recognized with Unbounded Error by Quantum Finite Automata. 410 0$aLecture notes in computer science ;$v5675. 410 0$aLNCS sublibrary.$nSL 1,$pTheoretical computer science and general issues. 517 3 $aCSR 2009 606 $aComputer science$vCongresses 606 $aComputer science$zRussia (Federation)$vCongresses 615 0$aComputer science 615 0$aComputer science 676 $a004.0151 701 $aFrid$b Anna$01358924 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910484414703321 996 $aComputer science -- theory and applications$94194727 997 $aUNINA