CSR 2008:
Moscow, Russia
Edward A. Hirsch, Alexander A. Razborov, Alexei L. Semenov, Anatol Slissenko (Eds.):
Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings.
Lecture Notes in Computer Science 5010 Springer 2008, ISBN 978-3-540-79708-1
Opening Lecture
- Avi Wigderson:
Randomness - A Computational Complexity Perspective.
1-2

Invited Papers
- Eric Allender:
Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds.
3-10

- Zurab Khasidashvili:
On Formal Equivalence Verification of Hardware.
11-12

- Pavel Pudlák:
Twelve Problems in Proof Complexity.
13-27

- Limsoon Wong:
Manifestation and Exploitation of Invariants in Bioinformatics.
28

- Uri Zwick:
Simple Stochastic Games, Mean Payoff Games, Parity Games.
29

Theory Track
- Sergei N. Artëmov, Elena Nogina:
Topological Semantics of Justification Logic.
30-39

- Vikraman Arvind, Bireswar Das, Johannes Köbler:
A Logspace Algorithm for Partial 2-Tree Canonization.
40-51

- Arnon Avron, Anna Zamansky:
A Triple Correspondence in Canonical Calculi: Strong Cut-Elimination, Coherence, and Non-deterministic Semantics.
52-63

- Maxim A. Babenko, Tatiana A. Starikovskaya:
Computing Longest Common Substrings Via Suffix Arrays.
64-75

- Nicolas Bedon, Alexis Bès, Olivier Carton, Chloe Rispal:
Logic and Rational Languages of Words Indexed by Linear Orderings.
76-85

- Markus Bläser, Holger Dell, Johann A. Makowsky:
Complexity of the Bollobás-Riordan Polynomial.
86-98

- Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino, Vladimir Oudalov:
A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2×2 Subgames.
99-109

- Didier Caucal, Stéphane Hassen:
Synchronization of Grammars.
110-121

- Dmitriy Yu. Cherukhin:
Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates.
122-133

- Ugo Dal Lago, Martin Hofmann:
A Semantic Proof of Polytime Soundness of Light Affine Logic.
134-145

- Rostislav Deviatov:
On Subword Complexity of Morphic Sequences.
146-157

- Jirí Fiala, Daniël Paulusma:
Comparing Universal Covers in Polynomial Time.
158-167

- Melvin Fitting:
S4LPand Local Realizability.
168-179

- Uffe Flarup, Laurent Lyaudet:
On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract).
180-193

- Enrico Formenti, Jarkko Kari, Siamak Taati:
The Most General Conservation Law for a Cellular Automaton.
194-203

- Sumit Ganguly:
Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract).
204-215

- Johannes Köbler, Oleg Verbitsky:
From Invariants to Canonization in Parallel.
216-227

- Roman Kuznets:
Self-referentiality of Justified Knowledge.
228-239

- Nutan Limaye, Meena Mahajan, Antoine Meyer:
On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata.
240-251

- Denis Osin, Vladimir Shpilrain:
Public Key Encryption and Encryption Emulation Attacks.
252-260

- Vladimir V. Podolskii:
A Uniform Lower Bound on Weights of Perceptrons.
261-272

- Yury Savateev:
Lambek Grammars with One Division Are Decidable in Polynomial Time.
273-282

- Vladimir Shpilrain:
Cryptanalysis of Stickel's Key Exchange Scheme.
283-288

- Arseny M. Shur:
Combinatorial Complexity of Regular Languages.
289-301

- Vladimir V. V'yugin:
On Sequences with Non-learnable Subsequences.
302-313

- Mingyu Xiao:
Algorithms for Multiterminal Cuts.
314-325

- Marius Zimand:
Two Sources Are Better Than One for Increasing the Kolmogorov Complexity of Infinite Sequences.
326-338

Applications and Technology Track
- Yevgeniy Bodyanskiy, Sergiy Popov, Taras Rybalchenko:
Multilayer Neuro-fuzzy Network for Short Term Electric Load Forecasting.
339-348

- Laura Kovács:
Invariant Generation for P-Solvable Loops with Assignments.
349-359

- Valery A. Nepomniaschy, Dmitri M. Beloglazov, Tatiana G. Churina, Mikhail Mashukov:
Using Coloured Petri Nets to Model and Verify Telecommunications Systems.
360-371

- Victor Y. Pan, Dmitriy Ivolgin, Brian Murphy, Rhys Eric Rosholt, Yuqing Tang, Xiaodong Yan:
Additive Preconditioning for Matrix Computations.
372-383

- Dusko Pavlovic:
Network as a Computer: Ranking Paths to Find Flows.
384-397

- Maxime Rebout, Louis Féraud, Sergei Soloviev:
A Unified Categorical Approach for Attributed Graph Rewriting.
398-409

Last update Wed May 22 23:08:41 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page