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

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