SOFSEM 2012: Theory and Practice of Computer Science: 38th Conference on Current Trends in Theory and Practice of Computer Science, à pindlerův Mlýn, Czech Republic, January 21-27, 2012. Proceedings

Content: 
Front Matter....Pages -
The Legacy of Turing in Numerical Analysis....Pages 1-13
Turing Machines for Dummies....Pages 14-30
What Is an Algorithm?....Pages 31-42
Strong Bridges and Strong Articulation Points of Directed Graphs....Pages 43-43
Towards Computational Models of Artificial Cognitive Systems That Can, in Principle, Pass the Turing Test....Pages 44-63
A Fully Generic Approach for Realizing the Adaptive Web....Pages 64-76
Multi Feature Indexing Network MUFIN for Similarity Search Applications....Pages 77-87
Recent Challenges and Ideas in Temporal Synthesis....Pages 88-98
Cryptography from Learning Parity with Noise....Pages 99-114
A Quick Tour of Word Sense Disambiguation, Induction and Related Approaches....Pages 115-129
Not Another Look at the Turing Test!....Pages 130-140
The Equational Theory of Weak Complete Simulation Semantics over BCCSP....Pages 141-152
Complexity Insights of the Minimum Duplication Problem....Pages 153-164
A Turing Machine Resisting Isolated Bursts of Faults....Pages 165-176
Properties of SLUR Formulae....Pages 177-189
Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs....Pages 190-201
Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration....Pages 202-213
Randomized Group Testing Both Query-Optimal and Minimal Adaptive....Pages 214-225
Complexity of Model Checking for Modal Dependence Logic....Pages 226-237
Multitape NFA: Weak Synchronization of the Input Heads....Pages 238-250
Visibly Pushdown Transducers with Look-Ahead....Pages 251-263
A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators....Pages 264-276
Consistent Consequence for Boolean Equation Systems....Pages 277-288
4-Coloring H-Free Graphs When H Is Small....Pages 289-300
Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts....Pages 301-312
A Fast Approximation Scheme for the Multiple Knapsack Problem....Pages 313-324
Counting Maximal Independent Sets in Subcubic Graphs....Pages 325-336
Iterated Hairpin Completions of Non-crossing Words....Pages 337-348
On the Approximation Ratio of the Path Matching Christofides Algorithm....Pages 349-360
Parikh’s Theorem and Descriptional Complexity....Pages 361-372
A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs....Pages 373-384
The Complexity of Small Universal Turing Machines: A Survey....Pages 385-405
A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3....Pages 406-418
Complete Problem for Perfect Zero-Knowledge Quantum Proof....Pages 419-430
An Algorithm for Probabilistic Alternating Simulation....Pages 431-442
Towards a Smart, Self-scaling Cooperative Web Cache....Pages 443-455
Named Entity Disambiguation Based on Explicit Semantics....Pages 456-466
Design Pattern Support Based on the Source Code Annotations and Feature Models....Pages 467-478
On the Formalization of UML Activities for Component-Based Protocol Design Specifications....Pages 479-491
Tree Based Domain-Specific Mapping Languages....Pages 492-504
RESTGroups for Resilient Web Services....Pages 505-517
Leveraging Microblogs for Resource Ranking....Pages 518-529
Inner Architecture of a Social Networking System....Pages 530-541
State Coverage: Software Validation Metrics beyond Code Coverage....Pages 542-553
Factorization for Component-Interaction Automata....Pages 554-565
Optimizing Segment Based Document Protection....Pages 566-575
Securing the Future — An Information Flow Analysis of a Distributed OO Language....Pages 576-587
Improving Watermark Resistance against Removal Attacks Using Orthogonal Wavelet Adaptation....Pages 588-599
MAK€– A System for Modelling, Optimising, and Analyzing Production in Small and Medium Enterprises....Pages 600-611
Knowledge Compilation with Empowerment....Pages 612-624
Cost-Sensitive Classification with Unconstrained Influence Diagrams....Pages 625-636
Modeling and Predicting Students Problem Solving Times....Pages 637-648
Generic Heuristic Approach to General Game Playing....Pages 649-660
The SiMoL Modeling Language for Simulation and (Re-)Configuration....Pages 661-672
Back Matter....Pages -