Computer Science -- Theory and Applications : First International Symposium on Computer Science in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings

by Grigoriev, Dima; Harrison, John; Hirsch, Edward A.

• ISBN13: 9783540341666
• ISBN10: 3540341668
• Format: Paperback
• Copyright: 2006-09-30
• Publisher: Springer Verlag

Summary

This book constitutes the refereed proceedings of the First International Symposium on Computer Science in Russia, CSR 2006, held in St. Petersburg, Russia in June 2006. The 35 revised full theory papers and 29 revised application papers presented together with 3 invited talks were carefully reviewed and selected from 279 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.

Table of Contents

Non-black-box techniques in cryptography	p. 1
Complexity of polynomial multiplication over finite fields	p. 2
Synchronous elastic circuits	p. 3
SZK proofs for black-box group problems	p. 6
Canonical decomposition of a regular factorial language	p. 18
Acyclic bidirected and skew-symmetric graphs : algorithms and structure	p. 23
Inductive type schemas as functors	p. 35
Unfolding synthesis of asynchronous automata	p. 46
Conjugacy and equivalence of weighted automata and functional transducers	p. 58
Applications of the linear matroid parity algorithm to approximating Steiner trees	p. 70
Tuples of disjoint NP-sets	p. 80
Constructive equivalence relations on computable probability measures	p. 92
Planar dimer tilings	p. 104
The complexity of equality constraint languages	p. 114
Window subsequence problems for compressed texts	p. 127
Efficient algorithms in zero-characteristic for a new model of representation of algebraic varieties	p. 137
Relativisation provides natural separations for resolution-based proof systems	p. 147
Bounded-degree forbidden patterns problems are constraint satisfaction problems	p. 159
Isolation and reducibility properties and the collapse result	p. 171
Incremental branching programs	p. 178
Logic of proofs for bounded arithmetic	p. 191
On a maximal NFA without mergible states	p. 202
Expressiveness of metric modalities for continuous time	p. 211
Extending Dijkstra's algorithm to maximize the shortest path by node-wise limited arc interdiction	p. 221
Weighted logics for traces	p. 235
On nonforgetting restarting automata that are deterministic and/or monotone	p. 247
Unwinding a non-effective cut elimination proof	p. 259
Enumerate and expand : improved algorithms for connected vertex cover and tree cover	p. 270
Shannon entropy vs. Kolmogorov complexity	p. 281
Language equations with symmetric difference	p. 292
On primitive recursive realizabilities	p. 304
Evidence reconstruction of epistemic modal logic S5	p. 313
Linear temporal logic with until and before on integer numbers, deciding algorithms	p. 322
On the frequency of letters in morphic sequences	p. 334
Functional equations in Shostak theories	p. 346
All semi-local longest common subsequences in subquadratic time	p. 352
Non-approximability of the randomness deficiency function	p. 364
Multi-agent explicit knowledge	p. 369
Polarized subtyping for sized types	p. 381
Neural-network based physical fields modeling techniques	p. 393
Approximate methods for constrained total variation minimization	p. 403
Dynamic isoline extraction for visualization of streaming data	p. 415
Improved technique of IP address fragmentation strategies for DoS attack traceback	p. 427
Performance comparison between backpropagation, neuro-fuzzy network, and SVM	p. 438
Evolutionary multi-objective optimisation by diversity control	p. 447
3D facial recognition using eigenface and cascade fuzzy neural networks : normalized facial image approach	p. 457
A new scaling kernel-based fuzzy system with low computational complexity	p. 466
Bulk synchronous parallel ML : semantics and implementation of the parallel juxtaposition	p. 475
A shortest path algorithm based on limited search heuristics	p. 487
A new hybrid directory scheme for shared memory multi-processors	p. 498
Manipulator path planning in 3-dimensional space	p. 505
Least likely to use : a new page replacement strategy for improving database management system response time	p. 514
Nonlinear visualization of incomplete data sets	p. 524
A review of race detection mechanisms	p. 534
Fuzzy-Q knowledge sharing techniques with expertness measures : comparison and analysis	p. 544
Explaining symbolic trajectory evaluation by giving it a faithful semantics	p. 555
Analytic modeling of channel traffic in n-cubes	p. 567
Capturing an intruder in the pyramid	p. 580
Speech enhancement in short-wave channel based on empirical mode decomposition	p. 591
Extended resolution proofs for conjoining BDDs	p. 600
Optimal difference systems of sets with multipliers	p. 612
Authentication mechanism using one-time password for 802.11 wireless LAN	p. 619
Optimizing personalized retrieval system based on Web ranking	p. 629
Instruction selection for ARM/thumb processors based on a multi-objective ant algorithm	p. 641
A new flow control algorithm for high speed computer network	p. 652
Nonlinear systems modeling and control using support vector machine technique	p. 660
Fast motif search in protein sequence databases	p. 670
Table of Contents provided by Blackwell. All Rights Reserved.