LEADER 05180nam 22008055 450 001 996465528903316 005 20230406060554.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 $a20100301d2009 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aComputer Science - Theory and Applications$b[electronic resource] $eFourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009, Proceedings /$fedited by Anna Frid, Andrei S. Morozov, Andrey Rybalchenko, Klaus W. Wagner 205 $a1st ed. 2009. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2009. 215 $a1 online resource (XIII, 369 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v5675 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$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v5675 606 $aComputer science 606 $aAlgorithms 606 $aMachine theory 606 $aComputer science?Mathematics 606 $aCoding theory 606 $aInformation theory 606 $aTheory of Computation 606 $aAlgorithms 606 $aFormal Languages and Automata Theory 606 $aMathematics of Computing 606 $aComputer Science Logic and Foundations of Programming 606 $aCoding and Information Theory 615 0$aComputer science. 615 0$aAlgorithms. 615 0$aMachine theory. 615 0$aComputer science?Mathematics. 615 0$aCoding theory. 615 0$aInformation theory. 615 14$aTheory of Computation. 615 24$aAlgorithms. 615 24$aFormal Languages and Automata Theory. 615 24$aMathematics of Computing. 615 24$aComputer Science Logic and Foundations of Programming. 615 24$aCoding and Information Theory. 676 $a004.0151 702 $aFrid$b Anna$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aMorozov$b Andrei S$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aRybalchenko$b Andrey$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aWagner$b Klaus W$4edt$4http://id.loc.gov/vocabulary/relators/edt 906 $aBOOK 912 $a996465528903316 996 $aComputer Science - Theory and Applications$92889860 997 $aUNISA