SOFSEM 2016 : theory and practice of computer science : 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 23-28, 2016, Proceedings

This book constitutes the proceedings of the 42nd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2016, held in Harrachov, Czech Republic, in January 2016. The 43 full papers presented in this volume were carefully reviewed and selected from 116 submissions. They are organized in topical sections named: foundations of computer science; software engineering: methods, tools, applications; and data, information, and knowledge engineering. The volume also contains 7 invited talks in full paper length. Front Matter....Pages I-XV Front Matter....Pages 1-1 Cryptography in a Quantum World....Pages 3-16 Relating Sublinear Space Computability Among Graph Connectivity and Related Problems....Pages 17-28 Learning Automatic Families of Languages....Pages 29-40 Front Matter....Pages 41-41 From ESSENCE to Theory Oriented Software Engineering....Pages 43-50 Incremental Queries and Transformations: From Concepts to Industrial Applications....Pages 51-59 Front Matter....Pages 61-61 Big Sequence Management: A glimpse of the Past, the Present, and the Future....Pages 63-80 Pay-as-you-go Data Integration: Experiences and Recurring Themes....Pages 81-92 Front Matter....Pages 93-93 Robust Recoverable Path Using Backup Nodes....Pages 95-106 On Contact Graphs with Cubes and Proportional Boxes....Pages 107-120 Orthogonal Layout with Optimal Face Complexity....Pages 121-133 L-Drawings of Directed Graphs....Pages 134-147 A Combinatorial Model of Two-Sided Search....Pages 148-160 On the Power of Laconic Advice in Communication Complexity....Pages 161-170 Using Attribute Grammars to Model Nested Workflows with Extra Constraints....Pages 171-182 A Natural Counting of Lambda Terms....Pages 183-194 Online Minimum Spanning Tree with Advice....Pages 195-207 Subsequence Automata with Default Transitions....Pages 208-216 Run-Time Checking Multi-threaded Java Programs....Pages 217-228 Online Graph Coloring with Advice and Randomized Adversary....Pages 229-240 Pseudoknot-Generating Operation....Pages 241-252 Front Matter....Pages 93-93 Capabilities of Ultrametric Automata with One, Two, and Three States....Pages 253-264 The Complexity of Paging Against a Probabilistic Adversary....Pages 265-276 On Parity Game Preorders and the Logic of Matching Plays....Pages 277-289 A PTAS for Scheduling Unrelated Machines of Few Different Types....Pages 290-301 Compacting a Dynamic Edit Distance Table by RLE Compression....Pages 302-313 Walking Automata in Free Inverse Monoids....Pages 314-328 Precedence Scheduling with Unit Execution Time is Equivalent to Parametrized Biclique....Pages 329-343 Grover’s Search with Faults on Some Marked Elements....Pages 344-355 Reachability Problems for PAMs....Pages 356-368 On the Effects of Nondeterminism on Ordered Restarting Automata....Pages 369-380 Quantum Walks on Two-Dimensional Grids with Multiple Marked Locations....Pages 381-391 How to Smooth Entropy?....Pages 392-403 Bounded TSO-to-SC Linearizability Is Decidable....Pages 404-417 Probabilistic Autoreductions....Pages 418-429 Front Matter....Pages 431-431 ABS: A High-Level Modeling Language for Cloud-Aware Programming....Pages 433-444 Aspect, Rich, and Anemic Domain Models in Enterprise Information Systems....Pages 445-456 Finding Optimal Compatible Set of Software Components Using Integer Linear Programming....Pages 457-468 Effective Parallel Multicore-Optimized K-mers Counting Algorithm....Pages 469-477 Meta-Evolution Style for Software Architecture Evolution....Pages 478-489 The Simulation Relation for Formal E-Contracts....Pages 490-502 Front Matter....Pages 503-503 Solving the Problem of Selecting Suitable Objective Measures by Clustering Association Rules Through the Measures Themselves....Pages 505-517 Survey on Concern Separation in Service Integration....Pages 518-531 Utilizing Vector Models for Automatic Text Lemmatization....Pages 532-543 Improving Keyword Extraction from Movie Subtitles by Utilizing Temporal Properties....Pages 544-555 Identification of Navigation Lead Candidates Using Citation and Co-Citation Analysis....Pages 556-568 Summarizing Online User Reviews Using Bicliques....Pages 569-579 Post-processing Association Rules: A Network Based Label Propagation Approach....Pages 580-591 Application of Multiple Sound Representations in Multipitch Estimation Using Shift-Invariant Probabilistic Latent Component Analysis....Pages 592-601 Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams....Pages 602-614 Evaluation of Static/Dynamic Cache for Similarity Search Engines....Pages 615-627 Back Matter....Pages 629-630