Ebook: Computer Science – Theory and Applications: 7th International Computer Science Symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3-7, 2012. Proceedings
Author: Vijay V. Vazirani (auth.) Edward A. Hirsch Juhani Karhumäki Arto Lepistö Michail Prilutskii (eds.)
- Tags: Algorithm Analysis and Problem Complexity, Logics and Meanings of Programs, Mathematical Logic and Formal Languages, Discrete Mathematics in Computer Science, Computation by Abstract Devices, Mathematics of Computing
- Series: Lecture Notes in Computer Science 7353
- Year: 2012
- Publisher: Springer-Verlag Berlin Heidelberg
- Edition: 1
- Language: English
- pdf
This book constitutes the proceedings of the 7th International Computer Science Symposium in Russia, CSR 2012, held in Nizhny Novgorod in July 2012. The 28 full papers presented in this volume were carefully reviewed and selected from 66 submissions. CSR 2012 was one of the events of the Alan Turing Year 2012, the topics dealt with cover substantial parts of theoretical computer science and its applications.
This book constitutes the proceedings of the 7th International Computer Science Symposium in Russia, CSR 2012, held in Nizhny Novgorod in July 2012.
The 28 full papers presented in this volume were carefully reviewed and selected from 66 submissions. CSR 2012 was one of the events of the Alan Turing Year 2012, the topics dealt with cover substantial parts of theoretical computer science and its appcliations.
This book constitutes the proceedings of the 7th International Computer Science Symposium in Russia, CSR 2012, held in Nizhny Novgorod in July 2012.
The 28 full papers presented in this volume were carefully reviewed and selected from 66 submissions. CSR 2012 was one of the events of the Alan Turing Year 2012, the topics dealt with cover substantial parts of theoretical computer science and its appcliations.
Content:
Front Matter....Pages -
Can the Theory of Algorithms Ratify the “Invisible Hand of the Market”?....Pages 1-5
Resilient Quicksort and Selection....Pages 6-17
General Quantitative Specification Theories with Modalities....Pages 18-30
The Complexity of Intersecting Finite Automata Having Few Final States....Pages 31-42
News about Semiantichains and Unichain Coverings....Pages 43-51
Checking Tests for Read-Once Functions over Arbitrary Bases....Pages 52-63
Approximating Minimum Power Edge-Multi-Covers....Pages 64-75
Computing All MOD-Functions Simultaneously....Pages 76-80
Bounded Synchronization Delay in Omega-Rational Expressions....Pages 81-88
Towards Optimal Degree-Distributions for Left-Perfect Matchings in Random Bipartite Graphs....Pages 89-98
Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGs....Pages 99-111
Worst-Case Optimal Priority Queues via Extended Regular Counters....Pages 112-124
The Complexity of Minor-Ancestral Graph Properties with Forbidden Pairs....Pages 125-137
Satisfiability Thresholds beyond k??XORSAT....Pages 138-147
Finding Vertex-Surjective Graph Homomorphisms....Pages 148-159
Broadcast Domination on Block Graphs in Linear Time....Pages 160-171
Characterizing Certain Topological Specifications....Pages 172-183
Descriptional Complexity of Operations on Alternating and Boolean Automata....Pages 184-195
Consistency of Multidimensional Combinatorial Substitutions....Pages 196-204
Two-Way Automata Characterizations of L/poly versus NL....Pages 205-216
Cutting through Regular Post Embedding Problems....Pages 217-228
On the Advice Complexity of the Set Cover Problem....Pages 229-240
Constraint Satisfaction with Counting Quantifiers....Pages 241-252
Space-Bounded Kolmogorov Extractors....Pages 253-265
Some Results on more Flexible Versions of Graph Motif....Pages 266-277
A Characterization of Cellular Automata Generated by Idempotents on the Full Shift....Pages 278-289
Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time....Pages 290-301
Boolean Composition of Visual Secret Sharing Schemes....Pages 302-313
Back Matter....Pages 314-325
....Pages -