SOFSEM 2025: Theory and Practice of Computer Science
Description
This book constitutes the proceedings of the 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, held in Bratislava, Slovak Republic, during January 20-23, 2025.
The 48 full papers presented in this book were carefully reviewed and selected from 109 submissions. They include original research from all areas of foundations of computer science and artificial intelligence focusing on AI-based algorithms and techniques, nature-inspired computing, machine learning theory, multi-agent algorithms and games, neural network theory, parallel and distributed computing, quantum computing, computability, decidability, classical and non-classical models of computation, computational complexity, computational learning, cryptographic techniques and security, data compression, data and pattern mining methods, discrete combinatorial optimization, automata, languages, machine models, rewriting systems, efficient data structures, graph structure and algorithms, logics of computation, robotics, and other relevant theory topics in computing and AI.More details
Other editions
Additional editions
Content
On Pumping Problems for Unary Regular Languages.- The Complexity of Graph Exploration Games.- A SUBSET-SUM Characterisation of the A-Hierarchy.- On the periodic decompositions of multidimensional configurations.- Quantum Algorithm for the Multiple String Matching Problem.- Parallel Peeling of Invertible Bloom Lookup Tables in a Constant Number of Rounds.- The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem.- Colorful 3-Rainbow Domination.- The Computational Complexity of Equilibria with Strategic Constraints.- Exact characterizations of non-commutative algebraic complexity without homogeneity.- Roman Hitting Set.- Visual Complexity of Point Set Mappings.- Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees.- Knowledge Neurons in the Knowledge Graph-based Link Prediction Models.- Disjoint covering of bipartite graphs with $s$-clubs.- Query Learning of Context-Deterministic and Congruential Context-Free Languages over Infinite Alphabets.- Minimal Schnyder Woods and Long Induced Paths in 3-Connected Planar Graphs.- DAG Scheduling in the BSP Model.- Incremental computation of the set of period sets.- Tolerant Testing and Distance Estimation for Distributions Under Memory Constraints.- Packed Acyclic Deterministic Finite Automata.- Holey Graphs: Very Large Betti Numbers are Testable.- Warm-Started QAOA with Aligned Mixers Converges Slowly Near the Poles of the Bloch Sphere.- Online Busy Time Scheduling with Untrusted Prediction.- Maximal $\alpha$-gapped Repeats in a Fibonacci String.