000 04731nam a22006375i 4500
001 978-3-642-03351-3
003 DE-He213
005 20240423125908.0
007 cr nn 008mamaa
008 100301s2009 gw | s |||| 0|eng d
020 _a9783642033513
_9978-3-642-03351-3
024 7 _a10.1007/978-3-642-03351-3
_2doi
050 4 _aQA75.5-76.95
072 7 _aUYA
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aUYA
_2thema
082 0 4 _a004.0151
_223
245 1 0 _aComputer Science - Theory and Applications
_h[electronic resource] :
_bFourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009, Proceedings /
_cedited by Anna Frid, Andrei S. Morozov, Andrey Rybalchenko, Klaus W. Wagner.
250 _a1st ed. 2009.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2009.
300 _aXIII, 369 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v5675
505 0 _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.
650 0 _aComputer science.
650 0 _aAlgorithms.
650 0 _aMachine theory.
650 0 _aComputer science
_xMathematics.
650 0 _aCoding theory.
650 0 _aInformation theory.
650 1 4 _aTheory of Computation.
650 2 4 _aAlgorithms.
650 2 4 _aFormal Languages and Automata Theory.
650 2 4 _aMathematics of Computing.
650 2 4 _aComputer Science Logic and Foundations of Programming.
650 2 4 _aCoding and Information Theory.
700 1 _aFrid, Anna.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
700 1 _aMorozov, Andrei S.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
700 1 _aRybalchenko, Andrey.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
700 1 _aWagner, Klaus W.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
710 2 _aSpringerLink (Online service)
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783642033506
776 0 8 _iPrinted edition:
_z9783642033520
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v5675
856 4 0 _uhttps://doi.org/10.1007/978-3-642-03351-3
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cSPRINGER
999 _c182848
_d182848