SOFSEM 2008: Theory and Practice of Computer Science: 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008. Proceedings

Andris Ambainis (auth.), Viliam Geffert, Juhani Karhumäki, Alberto Bertoni, Bart Preneel, Pavol Návrat, Mária Bieliková (eds.)354077565X, 9783540775652

This fascinating and up-to-date book constitutes the refereed proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2008, held in Nový Smokovec, Slovakia, in January 2008.

The 57 revised full papers, presented together with 10 invited contributions, were carefully reviewed and selected from 162 submissions.

The contributions are segmented into four topical sections on foundations of computer science; computing by nature; networks, security, and cryptography; and Web technologies.

All in all, this is a crucial text that covers some of the most important contemporary subjects in computer science, and as with many Springer publications it comes complete with online files and updates.

---

Table of contents :
Front Matter….Pages –
Quantum Random Walks – New Method for Designing Quantum Algorithms….Pages 1-4
Social Information Access: The Other Side of the Social Web….Pages 5-22
Designing Adaptive Web Applications….Pages 23-33
Best of Both: Using Semantic Web Technologies to Enrich User Interaction with the Web and Vice Versa….Pages 34-49
On the Hardness of Reoptimization….Pages 50-65
Describing Self-assembly of Nanostructures….Pages 66-73
On the Undecidability of the Tiling Problem….Pages 74-82
Remote Entrusting by Run-Time Software Authentication….Pages 83-97
Trusted Computing — Special Aspects and Challenges….Pages 98-117
Optimizing Winning Strategies in Regular Infinite Games….Pages 118-123
Recursive Domain Equations of Filter Models….Pages 124-135
Algorithmic Problems for Metrics on Permutation Groups….Pages 136-147
Periodic and Infinite Traces in Matrix Semigroups….Pages 148-161
From Asynchronous to Synchronous Specifications for Distributed Program Synthesis….Pages 162-173
Exact OBDD Bounds for Some Fundamental Functions….Pages 174-185
Clustering-Based Similarity Search in Metric Spaces with Sparse Spatial Centers….Pages 186-197
A Useful Bounded Resource Functional Language….Pages 198-210
On Reachability Games of Ordinal Length….Pages 211-221
An Algorithm for Computation of the Scene Geometry by the Log-Polar Area Matching Around Salient Points….Pages 222-233
The Power of Tokens: Rendezvous and Symmetry Detection for Two Mobile Agents in a Ring….Pages 234-246
How Much Information about the Future Is Needed?….Pages 247-258
On Compiling Structured Interactive Programs with Registers and Voices….Pages 259-270
Optimal Orientation On-Line….Pages 271-279
Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality….Pages 280-291
Assisted Problem Solving and Decompositions of Finite Automata….Pages 292-303
Energy-Efficient Windows Scheduling….Pages 304-315
A New Model to Solve the Swap Matching Problem and Efficient Algorithms for Short Patterns….Pages 316-327
Certification of Proving Termination of Term Rewriting by Matrix Interpretations….Pages 328-339
Extension of Rescheduling Based on Minimal Graph Cut….Pages 340-351
Deriving Complexity Results for Interaction Systems from 1-Safe Petri Nets….Pages 352-363
Computing Longest Common Substring and All Palindromes from Compressed Strings….Pages 364-375
Basic Sets in the Digital Plane….Pages 376-387
Algebraic Optimization of Relational Queries with Various Kinds of Preferences….Pages 388-399
Mortality Problem for 2×2 Integer Matrices….Pages 400-405
Element Distinctness and Sorting on One-Tape Off-Line Turing Machines….Pages 406-417
Improved Bounds for Range Mode and Range Median Queries….Pages 418-423
An Automata Theoretic Approach to Rational Tree Relations….Pages 424-435
Slicing Petri Nets with an Application to Workflow Verification….Pages 436-447
Lower Bound for the Length of Synchronizing Words in Partially-Synchronizing Automata….Pages 448-459
Verifying Parameterized taDOM+ Lock Managers….Pages 460-472
Untangling a Planar Graph….Pages 473-484
Quantum Walks with Multiple or Moving Marked Locations….Pages 485-496
Parallel Immune System for Graph Coloring….Pages 497-505
The Quantum Complexity of Group Testing….Pages 506-518
Quantum Walks: A Markovian Perspective….Pages 519-530
A Memetic Algorithm for Global Induction of Decision Trees….Pages 531-540
Geometric Rates of Approximation by Neural Networks….Pages 541-550
A Sensitive Metaheuristic for Solving a Large Optimization Problem….Pages 551-559
Domain Name System as a Memory and Communication Medium….Pages 560-571
Strong Authentication over Lock-Keeper….Pages 572-584
Short Ballot Assumption and Threeballot Voting Protocol….Pages 585-598
Practical Deniable Encryption….Pages 599-609
Taming of Pict….Pages 610-621
Classification, Formalization and Verification of Security Functional Requirements….Pages 622-633
ONN the Use of Neural Networks for Data Privacy….Pages 634-645
Threshold Privacy Preserving Keyword Searches….Pages 646-658
3D_XML: A Three-Dimensional XML-Based Model….Pages 659-671
Visual Exploration of RDF Data….Pages 672-683
Creation, Population and Preprocessing of Experimental Data Sets for Evaluation of Applications for the Semantic Web….Pages 684-695
Algorithm for Intelligent Prediction of Requests in Business Systems….Pages 696-707
Mining Personal Social Features in the Community of Email Users….Pages 708-719
Proofs of Communication and Its Application for Fighting Spam….Pages 720-730
Web Pages Reordering and Clustering Based on Web Patterns….Pages 731-742
Compression of Concatenated Web Pages Using XBW….Pages 743-754
The Dynamic Web Presentations with a Generality Model on the News Domain….Pages 755-765
A Highly Efficient XML Compression Scheme for the Web….Pages 766-777
Improving Semantic Search Via Integrated Personalized Faceted and Visual Graph Navigation….Pages 778-789
Back Matter….Pages –