LEADER 06386nam 22008295 450 001 9910484414703321 005 20251226202819.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(BIP)27347532 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 $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 08$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 byLearning 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. 330 $aThe 4th International Computer Science Symposium in Russia (CSR 2009) was held August 18-23,2009 in Novosibirsk,Russia, hosted by the Sobolev Institute of Mathematics and Novosibirsk State University. It was the fourth event in the series of regular international meetings, following CSR 2006 in St. Petersburg, CSR 2007 in Ekaterinburg, and CSR 2008 in Moscow. The opening lecture was given by Andrei Voronkov, and four other invited plenary lectures were given by Sergei Odintsov, Wolfgang Thomas, Nikolai Vereshchagin, and Hongseok Yang. This volume contains all the accepted papers and some of the abstracts of the invited speakers. The scope of the proposed topics for the symposium was quite broad and covered basically all areas of computer science. We received 66 papers in total, and the Program Committee selected 29. Yandex provided the Best Student Paper Awards; the recepients of these awards were selected by the Program Committee: - Dmitry Itsykson, "Structural complexity of AvgBPP" - Yuri Pritykin and Julya Ulyashkina, "Aperiodicity measure for in'nite sequences." The reviewing processwasorganizedusing the EasyChairconferencesystem, created by Andrei Voronkov. We are grateful to our sponsors: - Russian Foundation for Basic Research - Yandex (the largest Russian Internet portal providing key Web services). We also thank the group of local organizers and in particular Pavel Salimov. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v5675 606 $aComputer science 606 $aAlgorithms 606 $aMachine theory 606 $aComputer science$xMathematics 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$xMathematics. 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 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