Computer Science - Theory and Applications [[electronic resource] ] : Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009, Proceedings / / edited by Anna Frid, Andrei S. Morozov, Andrey Rybalchenko, Klaus W. Wagner |
Edizione | [1st ed. 2009.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2009 |
Descrizione fisica | 1 online resource (XIII, 369 p.) |
Disciplina | 004.0151 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Computer science
Algorithms Machine theory Computer science—Mathematics Coding theory Information theory Theory of Computation Formal Languages and Automata Theory Mathematics of Computing Computer Science Logic and Foundations of Programming Coding and Information Theory |
ISBN |
1-280-38317-8
9786613561091 3-642-03351-2 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | 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. |
Record Nr. | UNISA-996465528903316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2009 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Computer 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.) |
Edizione | [1st ed. 2009.] |
Pubbl/distr/stampa | Berlin ; ; New York, : Springer, c2009 |
Descrizione fisica | 1 online resource (XIII, 369 p.) |
Disciplina | 004.0151 |
Altri autori (Persone) | FridAnna |
Collana |
Lecture notes in computer science
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
Soggetto topico |
Computer science
Computer science - Russia (Federation) |
ISBN |
1-280-38317-8
9786613561091 3-642-03351-2 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | 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. |
Altri titoli varianti | CSR 2009 |
Record Nr. | UNINA-9910484414703321 |
Berlin ; ; New York, : Springer, c2009 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|