This bookconstitutes the proceedings of the 42nd International Conference on CurrentTrends in Theory and Practice of Computer Science, SOFSEM 2016, held inHarrachov, Czech Republic, in January 2016.The 43 fullpapers presented in this volume were carefully reviewed and selected from 116submissions. They are organized in topical sections named: foundations ofcomputer science; software engineering: methods, tools, applications; and datainformation, and knowledge engineering. The volume also contains 7 invitedtalks in full paper length.

Foundations of Computer Science.- Cryptographyin a Quantum World.- Relating Sublinear Space Computability among GraphConnectivity and Related Problems.- Learning Automatic Families of Languages.- SoftwareEngineering: Methods, Tools, Applications From ESSENCE to Theory OrientedSoftware Engineering.- Incremental Queries and Transformations: From Concepts toIndustrial Applications.- Data, Information, and Knowledge Engineering BigSequence Management: A Glimpse on the Past, the Present, and the Future.- Pay-as-you-goData Integration: Experiences and Recurring Themes.- Foundations of ComputerScience.- Robust Recoverable Path Using Backup Nodes.- On Contact Graphs withCubes and Proportional Boxes.- Orthogonal Layout with Optimal Face Complexity.L-Drawings of Directed Graphs.- A Combinatorial Model of Two-sided Search.- Onthe Power of Laconic Advice in Communication Complexity.- Using AttributeGrammars to Model Nested Workflows with Extra Constraints.- A Natural Countingof Lambda Terms.- Online Minimum Spanning Tree with Advice.- Subsequence Automatawith Default Transitions.- Run-Time Checking Multi-threaded Java Programs.- OnlineGraph Coloring with Advice and Randomized Adversary.- Pseudoknot-GeneratingOperation.- Capabilities of Ultrametric Automata with One, Two, and ThreeStates.- The Complexity of Paging Against a Probabilistic Adversary.- On ParityGame Preorders and the Logic of Matching Plays.- A PTAS for SchedulingUnrelated Machines of Few Different Types.- Compacting a Dynamic Edit DistanceTable by RLE Compression.- Walking Automata in Free Inverse Monoids.- PrecedenceScheduling with Unit Execution Time is Equivalent to Parametrized Biclique.- Grover'sSearch with Faults on Some Marked Elements.- Reachability problems for PAMs.- Onthe Effects of Nondeterminism on Ordered Restarting Automata.- Quantum Walks onTwo-Dimensional Grids with Multiple Marked Locations.- How to Smooth Entropy?.Bounded TSO-to-SC Linearizability is Decidable.- Probabilistic Autoreductions.Software Engineering: Methods, Tools, Applications ABS: A High-Level Modeling Language forCloud-Aware Programming.- Aspect, Rich, and Anemic Domain Models in Enterprise InformationSystems.- Finding Optimal Compatible Set of Software Components Using Integer LinearProgramming.- Effective Parallel Multicore-optimized K-mers CountingAlgorithm.- Meta-Evolution Style for Software Architecture Evolution.- TheSimulation Relation for Formal e-contracts.- Data, Information, and KnowledgeEngineering Solving the Problem of Selecting Suitable Objective Measures by ClusteringAssociation Rules through the Measures Themselves.- Survey On Concern Separationin Service Integration.- Utilizing Vector Models for Automatic TextLemmatization.- Improving Keyword Extraction from Movie Subtitles by Utilizing Temporal Properties.- Identification ofNavigation Lead Candidates Using Citation and Co-Citation Analysis.- SummarizingOnline User Reviews Using Bicliques.-Post-Processing Association Rules: aNetwork Based Label Propagation Approach.- Application of Multiple SoundRepresentations in Multipitch Estimation Using Shift-Invariant ProbabilisticLatent Component Analysis.- Projection for Nested Word Automata Speeds up XPathEvaluation on XML Streams.- Evaluation of Static/Dynamic Cache for SimilaritySearch Engines.