This book constitutes the refereed proceedings of the Second International Symposium on Computer Science in Russia, CSR 2007, held in Ekaterinburg, Russia, September 3-7, 2007
The 35 revised papers presented were carefully reviewed and selected from 95 submissions. All major areas in computer science are addressed; the theory track deals with algorithms, protocols, and data structures; complexity and cryptography; formal languages, automata and their applications to computer science; computational models and concepts; proof theory and applications of logic to computer science. The application part comprises programming and languages; computer architecture and hardware design; symbolic computing and numerical applications; application software; artificial intelligence and robotics.
Author(s): Yuri Gurevich (auth.), Volker Diekert, Mikhail V. Volkov, Andrei Voronkov (eds.)
Series: Lecture Notes in Computer Science 4649
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2007
Language: English
Pages: 420
Tags: Theory of Computation; Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Computing Methodologies; Mathematics of Computing; Bioinformatics
Front Matter....Pages -
Proving Church’s Thesis....Pages 1-3
The Limits of Quantum Computers....Pages 4-4
Marrying Words and Trees....Pages 5-5
TPTP, TSTP, CASC, etc.....Pages 6-22
Abstract Modeling and Formal Verification of Microprocessors....Pages 23-23
Sequences of Level 1, 2, 3,..., k ,.......Pages 24-32
Timers and Proximities for Mobile Ambients....Pages 33-43
Pushing Random Walk Beyond Golden Ratio....Pages 44-55
Reversible Machine Code and Its Abstract Processor Architecture....Pages 56-69
A Fast Algorithm for Path 2-Packing Problem....Pages 70-81
Decidability of Parameterized Probabilistic Information Flow....Pages 82-91
Inverting Onto Functions and Polynomial Hierarchy....Pages 92-103
Proved-Patterns-Based Development for Structured Programs....Pages 104-114
Planarity, Determinants, Permanents, and (Unique) Matchings....Pages 115-126
Equivalence Problems for Circuits over Sets of Natural Numbers....Pages 127-138
Bouillon: A Wiki-Wiki Social Web....Pages 139-145
A PDL-Like Logic of Knowledge Acquisition....Pages 146-157
Resource Placement in Networks Using Chromatic Sets of Power Graphs....Pages 158-167
Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth....Pages 168-181
Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems....Pages 182-193
New Bounds for MAX-SAT by Clause Learning....Pages 194-204
Towards Hierarchical Clustering (Extended Abstract)....Pages 205-215
Estimation of the Click Volume by Large Scale Regression Analysis....Pages 216-226
Maximal Intersection Queries in Randomized Graph Models....Pages 227-236
A Note on Specialization of Interpreters....Pages 237-248
Efficient Computation in Groups Via Compression....Pages 249-258
Constructing a Secret Binary Partition of a Digital Image Robust to a Loss of Synchronization....Pages 259-268
On the Complexity of Matrix Rank and Rigidity....Pages 269-280
On the Usage of Clustering for Content Based Image Retrieval....Pages 281-289
Performance Modeling of Wormhole Hypermeshes Under Hotspot Traffic....Pages 290-302
Application of Modified Coloured Petri Nets to Modeling and Verification of SDL Specified Communication Protocols....Pages 303-314
Symmetry of Information and Nonuniform Lower Bounds....Pages 315-327
Perceptrons of Large Weight....Pages 328-336
A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes....Pages 337-348
Kolmogorov Complexity, Lovász Local Lemma and Critical Exponents....Pages 349-355
Generic Complexity of Presburger Arithmetic....Pages 356-361
Everywhere α -Repetitive Sequences and Sturmian Words....Pages 362-372
Timed Traces and Strand Spaces....Pages 373-386
On Empirical Meaning of Randomness with Respect to a Real Parameter....Pages 387-396
An Efficient Algorithm for Zero-Testing of a Lacunary Polynomial at the Roots of Unity....Pages 397-406
Generic Complexity of Undecidable Problems....Pages 407-417
Back Matter....Pages -
