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

This book constitutes the refereed proceedings of the 38th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2012, held in � pindlerův Mlýn, Czech Republic, in January 2012. The 43 revised papers presented in this volume were carefully reviewed and selected from 121 submissions. The book also contains 11 invited talks, 10 of which are in full-paper length. The contributions are organized in topical sections named: foundations of computer science; software and Web engineering; cryptography, security, and verification; and artificial intelligence. 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 - Annotation This book constitutes the refereed proceedings of the 38th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2012, held in pindlerv Mlýn, Czech Republic, in January 2012. The 43 revised papers presented in this volume were carefully reviewed and selected from 121 submissions. The book also contains 11 invited talks, 10 of which are in full-paper length. The contributions are organized in topical sections named: foundations of computer science; software and Web engineering; cryptography, security, and verification; and artificial intelligence This book constitutes the refereed proceedings of the 38th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2012, held in Špindlerův Mlýn, Czech Republic, in January 2012. The 43 revised papers presented in this volume were carefully reviewed and selected from 121 submissions. The book also contains 11 invited talks, 10 of which are in full-paper length. The contributions are organized in topical sections named: foundations of computer science; software and Web engineering; cryptography, security, and verification; and artificial intelligence This book constitutes the refereed proceedings of the 38th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2012, held in Spindleruv Mlyn, Czech Republic, in January 2012. The contributions are organized in topical sections named: foundations of computer science;