04224nam 2200601Ia 450 991048441470332120200520144314.01-280-38317-897866135610913-642-03351-210.1007/978-3-642-03351-3(CKB)1000000000772858(SSID)ssj0000316893(PQKBManifestationID)11251766(PQKBTitleCode)TC0000316893(PQKBWorkID)10286410(PQKB)10317651(DE-He213)978-3-642-03351-3(MiAaPQ)EBC3064435(PPN)13995080X(EXLCZ)99100000000077285820090811d2009 uy 0engurnn|008mamaatxtccrComputer science -- theory and applications fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009 : proceedings /Anna Frid ... [et al.] (eds.)1st ed. 2009.Berlin ;New York Springerc20091 online resource (XIII, 369 p.) Lecture notes in computer science,0302-9743 ;5675LNCS sublibrary. SL 1, Theoretical computer science and general issuesBibliographic Level Mode of Issuance: Monograph3-642-03350-4 Includes bibliographical references and index.Invited 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.Lecture notes in computer science ;5675.LNCS sublibrary.SL 1,Theoretical computer science and general issues.CSR 2009Computer scienceCongressesComputer scienceRussia (Federation)CongressesComputer scienceComputer science004.0151Frid Anna1358924MiAaPQMiAaPQMiAaPQBOOK9910484414703321Computer science -- theory and applications4194727UNINA