Computer Science – Theory and Applications: Third International Computer Science Symposium in Russia, CSR 2008 Moscow, Russia, June 7-12, 2008 Proceedings

Front Matter....Pages -
Randomness – A Computational Complexity Perspective....Pages 1-2
Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds....Pages 3-10
On Formal Equivalence Verification of Hardware....Pages 11-12
Twelve Problems in Proof Complexity....Pages 13-27
Manifestation and Exploitation of Invariants in Bioinformatics....Pages 28-28
Simple Stochastic Games, Mean Payoff Games, Parity Games....Pages 29-29
Topological Semantics of Justification Logic....Pages 30-39
A Logspace Algorithm for Partial 2-Tree Canonization....Pages 40-51
A Triple Correspondence in Canonical Calculi: Strong Cut-Elimination, Coherence, and Non-deterministic Semantics....Pages 52-63
Computing Longest Common Substrings Via Suffix Arrays....Pages 64-75
Logic and Rational Languages of Words Indexed by Linear Orderings....Pages 76-85
Complexity of the Bollobás-Riordan Polynomial....Pages 86-98
A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2×2 Subgames....Pages 99-109
Synchronization of Grammars....Pages 110-121
Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates....Pages 122-133
A Semantic Proof of Polytime Soundness of Light Affine Logic....Pages 134-145
On Subword Complexity of Morphic Sequences....Pages 146-157
Comparing Universal Covers in Polynomial Time....Pages 158-167
 S4LP and Local Realizability....Pages 168-179
On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)....Pages 180-193
The Most General Conservation Law for a Cellular Automaton....Pages 194-203
Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)....Pages 204-215
From Invariants to Canonization in Parallel....Pages 216-227
Self-referentiality of Justified Knowledge....Pages 228-239
On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata....Pages 240-251
Public Key Encryption and Encryption Emulation Attacks....Pages 252-260
A Uniform Lower Bound on Weights of Perceptrons....Pages 261-272
Lambek Grammars with One Division Are Decidable in Polynomial Time....Pages 273-282
Cryptanalysis of Stickel’s Key Exchange Scheme....Pages 283-288
Combinatorial Complexity of Regular Languages....Pages 289-301
On Sequences with Non-learnable Subsequences....Pages 302-313
Algorithms for Multiterminal Cuts....Pages 314-325
Two Sources Are Better Than One for Increasing the Kolmogorov Complexity of Infinite Sequences....Pages 326-338
Multilayer Neuro-fuzzy Network for Short Term Electric Load Forecasting....Pages 339-348
Invariant Generation for P-Solvable Loops with Assignments....Pages 349-359
Using Coloured Petri Nets to Model and Verify Telecommunications Systems....Pages 360-371
Additive Preconditioning for Matrix Computations....Pages 372-383
Network as a Computer: Ranking Paths to Find Flows....Pages 384-397
A Unified Categorical Approach for Attributed Graph Rewriting....Pages 398-409
Back Matter....Pages -