SOFSEM 2019: Theory and Practice of Computer Science

Name: SOFSEM 2019: Theory and Practice of Computer Science | 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings

Barbara Catania Rastislav Královic Jerzy Nawrocki Giovanni Pighizzini(Herausgeber*in)

Springer (Verlag)

Erschienen am 10. Januar 2019

XIII, 534 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-030-10801-4 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Organization
Contents
Cross-Layer Adaptation in Multi-layer Autonomic Systems (Invited Talk)
1 Introduction
2 State of the Art
2.1 Multi-layer Autonomic Systems
2.2 Examples of MuLAS
2.3 Background in Programming Technology
3 Consistent Multi-layer Variation of Autonomic Controllers with Cross-Cutting Contexts
4 Cross-Layer Self-optimization in Multi-layer Autonomic Systems
5 Energy-Aware Self-optimization in Energy-Proportional Servers
6 Conclusion
References
Distance-Based Community Search (Invited Talk Extended Abstract)
1 Community Search
2 The Minimum Wiener Connector
3 The Minimum Inefficiency Subgraph
4 Adaptive Community Search in Dynamic Networks
References
Minicomplexity
1 Machines vs. Machines
2 Problems vs. Problems
2.1 RETROCOUNT
2.2 PROJECTION
2.3 MEMBERSHIP
2.4 LIST MEMBERSHIP
3 Modular Witnesses
References
Action Research in Software Engineering: Metrics' Research Perspective (Invited Talk)
1 Introduction - What Action Research Is
2 The Phases of Action Research Projects
2.1 Diagnosing
2.2 Action Planning
2.3 Action Taking
2.4 Evaluation
2.5 Learning
3 Maximizing Impact - Who Should be a Part of the Action Team
4 Metrics Action Research
5 Conclusions: The Future of Action Research
References
From Big Data to Big Knowledge
1 Information Extraction
2 Probabilistic Databases
3 Distributed Graph Databases
References
Sorting Networks on Restricted Topologies
1 Introduction
2 Definitions
3 Our Results
4 Routing via Matchings
4.1 Routing on Subgraphs of G
5 General Upper Bounds on st(G)
6 Bounds on Concrete Graph Families
6.1 The Pyramid Graph
References
Minimum Reload Cost Graph Factors
1 Introduction
2 Preliminaries
3 Classical Complexity of r-MRCF
4 Parameterized Complexity of r-MRCF
References
Stable Divisorial Gonality is in NP
1 Introduction
2 Preliminaries
3 A (Partial) Certificate
4 Correctness
5 A Bound on Subdivisions
6 Conclusion
References
Coalition Resilient Outcomes in Max k-Cut Games
1 Introduction
2 Preliminaries
3 Non-existence of a Minimal Strong Potential Function
4 The Existence of a 5-SE in Unweighted Graphs
5 Local Strong Equilibria
6 Existence of SE for Special Cases
7 Conclusions and Future Work
References
Phase Transition in Matched Formulas and a Heuristic for Biclique Satisfiability
1 Introduction
2 Definitions and Related Results
2.1 Graph Theory
2.2 Boolean Formulas
2.3 Matched Formulas
2.4 Biclique Satisfiable Formulas
2.5 Generating Experimental Data
3 Phase Transition on Matched Formulas
4 Bounded Biclique Cover Heuristic
4.1 Description of Heuristic Algorithm
4.2 Experimental Evaluation of Heuristic Algorithm
5 Bounded Biclique SAT Encoding
5.1 Description of SAT Encoding
5.2 Experimental Evaluation of Heuristic Algorithm
5.3 Experimental Environment
6 Conclusion
References
On Infinite Prefix Normal Words
1 Introduction
2 Basics
3 A Characterization of Periodic and Aperiodic Prefix Normal Words with Respect to Minimum Density
4 Sturmian Words and Prefix Normal Words
4.1 From Flipext to Lazy--Flipext
5 Prefix Normal Words, Prefix Normal Forms, and Abelian Complexity
5.1 Balanced and c-Balanced Words
5.2 Prefix Normal Forms and Abelian Complexity
5.3 Prefix Normal Forms of Sturmian Words
6 Prefix Normal Words and Lexicographic Order
References
Priority Scheduling in the Bamboo Garden Trimming Problem
1 Introduction
2 Notation
3 Theoretical Results
3.1 Priority Schedulings
3.2 ReduceMax Scheduling
4 Experimental Results
5 Conclusion
References
Patrolling on Dynamic Ring Networks
1 Introduction
2 Model
3 Preliminaries
4 Patrolling with Local Visibility
5 Two Agents with Global Visibility
5.1 UNKNOWN Setting
5.2 KNOWN Setting
6 Patrolling with k&2 Agents Having Global Visibility
6.1 UNKNOWN Setting: Generalising TICK-TOCK for k Agents
6.2 KNOWN Setting: PLACE-&-SWIPE for k Agents
7 Conclusion
References
Gathering of Robots in a Grid with Mobile Faults
1 Introduction
2 Our Model
3 Agents with Global Visibility
3.1 Impossibility Result for Two Honest Agents
3.2 Gathering of Three Honest Agents
4 Agents with Local Visibility
5 Conclusions
References
Probabilistic Parameterized Polynomial Time
1 Preliminaries
2 Error Parameterization
3 Reductions and Completeness
4 Application of Results
5 Closing Remarks
References
On Matrix Ins-Del Systems of Small Sum-Norm
1 Introduction
2 Preliminaries
2.1 Matrix Insertion-Deletion Systems
2.2 Regular Closure of Linear Languages
3 Computational Completeness Results
4 Describing the Regular Closure of Linear Languages
5 Conclusion
References
Separation Logic with Linearly Compositional Inductive Predicates and Set Data Constraints
1 Introduction
2 Logics for Sets
3 Linearly Compositional SLID with Set Data Constraints
4 Satisfiability of SLIDSLC [P]
5 Transitive Closure of Difference-Bound Set Relations
6 Satisfiability of RQSPA
7 Conclusion
References
On the Complexity of Optimal Matching Reconfiguration
1 Introduction
2 Preliminaries
3 NP-Hardness of Optimal Reconfiguration
4 An Exact Algorithm for Optimal Reconfiguration
5 Concluding Remarks
References
Forbidden Directed Minors, Directed Path-Width and Directed Tree-Width of Tree-Like Digraphs
1 Introduction
2 Preliminaries
3 Directed Cactus Forests and Pseudoforests
4 Directed Graph Minors of Tree-Like Digraphs
5 Directed Path-Width of Tree-Like Digraphs
6 Directed Tree-Width of Tree-Like Digraphs
7 Conclusion and Outlook
References
Existence Versus Exploitation: The Opacity of Backdoors and Backbones Under a Weak Assumption
1 Introduction
2 Definitions and Notations
3 Results on Backdoors to CNF Formulas
4 Results on Backbones
5 Conclusions
References
On Point Set Embeddings for k-Planar Graphs with Few Bends per Edge
1 Introduction
2 Preliminaries
3 1-Plane Graphs
4 2-Plane Graphs
5 k-Plane Graphs
6 Discussions and Conclusions
References
Enumerating Connected Induced Subgraphs: Improved Delay and Experimental Comparison
1 Introduction
2 Preliminaries and Main Algorithm
3 Polynomial Delay with Simple
4 Polynomial Delay with Pivot
5 An Experimental Comparison
References
Multi-stranded String Assembling Systems
1 Introduction
2 Preliminaries and Definitions
3 Single-Stranded SAS
4 String Assembling Systems with Multiple Strands
References
Towards Automatic Comparison of Cloud Service Security Certifications
Abstract
1 The Problem Domain
1.1 Proposed Automatic Comparison
1.2 Organization of This Paper
2 Formalizing Certification Schemes Using Ontology
3 Employing Natural Language Processing
4 Prototype Implementation and Results
5 Looking Ahead
Acknowledgement
References
On the Expressive Power of GF(2)-Grammars
1 Introduction
2 GF(2)-Grammars
3 GF(2)-Grammars over the Unary Alphabet
4 Representability of Subsets of a* b*
5 A Separating Example and the Hierarchy
6 Closure Properties
7 Hardest Language
8 Conclusion
References
An Efficient Algorithm for Combining Verification and Validation Methods
Abstract
1 Introduction
2 Background and Related Work
2.1 Quality Characteristics
2.2 V&V Methods
2.3 Combination of V&V Methods
3 Modeling the Problem
4 Parameterized Complexity
4.1 Fixed-Parameter Tractable (FPT) Approach
4.2 Scalability of the FPT-Algorithms
5 FPT-Algorithm to Combine V&V Methods
5.1 Execution of the Set Cover Algorithm
5.2 Running Time Analysis
6 Computational Experiments
7 Discussion
8 Concluding Remarks
Acknowledgment
References
Robustness Radius for Chamberlin-Courant on Restricted Domains
1 Introduction
2 Preliminaries
3 XP Algorithms for Robustness Radius
4 Hardness for -Crossing Profiles
5 Concluding Remarks and Open Problems
References
On the Complexity of Color-Avoiding Site and Bond Percolation
1 Introduction and Related Works
2 Modeling Shared Vulnerabilities in Networks
2.1 Coloring the Edges
2.2 Coloring the Vertices
3 Computational Complexity of Finding the Color-Avoiding Components
4 Conclusion
References
Lackadaisical Quantum Walks with Multiple Marked Vertices
1 Introduction
2 Quantum Walk on the Two-Dimensional Grid
2.1 Regular (Non-lackadaisical) Quantum Walk
2.2 Lackadaisical Quantum Walk
3 Stationary States of the Lackadaisical Quantum Walk
4 Optimality of l for Multiple Marked Vertices
5 Conclusions
References
A 116/13-Approximation Algorithm for L(2,1)-Labeling of Unit Disk Graphs
1 Introduction
2 Preliminaries
2.1 Definitions and Notations
2.2 Unit Disk Graphs (UDG)
3 Basic Results and an Existing Algorithms
3.1 Upper and Lower Bounds on L(2, 1)-Labeling Numbers
3.2 Existing Algorithms and Its Improvement
4 116/13-Approximation Algorithm
4.1 Square Division and Basic Labeling
4.2 Necessary Condition for = 2- 1
4.3 2-Phase Labeling
4.4 Overall Algorithm and Approximation Ratio
References
Minimizing the Cost of Team Exploration
1 Introduction
2 Notation
3 Rings in the Off-Line Setting
4 Rings in the On-Line Setting
5 Tree in the Off-Line Setting
5.1 The Algorithm
5.2 Analysis of the Algorithm
6 Tree in the On-Line Setting
7 Conclusion
References
Two-Head Finite-State Acceptors with Translucent Letters
1 Introduction
2 Preliminaries
3 Two-Head Finite-State Acceptors with Translucent Letters
4 Linear Context-Free Trace Languages
5 Further Closure Properties and Decidability Results
6 Conclusion
References
Do Null-Type Mutation Operators Help Prevent Null-Type Faults?
1 Introduction
2 Background and Related Work
3 Experimental Setup
3.1 Null-Type Mutation Operators
3.2 Case Study
4 Results and Discussion
5 Threats to Validity
6 Conclusion
References
Towards Combining Multitask and Multilingual Learning
1 Introduction
2 Related Work
3 Proposed Method
3.1 Architecture
3.2 Training
4 Experiments and Results
4.1 Datasets
4.2 Experiment
4.3 Sharing the Output Layer
5 Future Work and Conclusion
References
On the Size of Logical Automata
1 Introduction
1.1 Logical Automata
1.2 A Complete Family of Languages
1.3 Definitions
1.4 Related Results
2 Main Results
2.1 General Approach
2.2 Lower Bounds
2.3 Upper Bounds
A Wrong Proof in Previous Work
References
Bayesian Root Cause Analysis by Separable Likelihoods
1 Introduction
1.1 Anomaly Detection and Root Cause Analysis
1.2 Contribution
1.3 Organization
2 Separable Posteriors
2.1 Dirichlet-Multinomial Model
2.2 BNB Model
3 Root Cause Analysis of Anomalies
3.1 Generative Model
3.2 RCA for Projects
3.3 RCA for Procedures and Error Messages
4 Conclusion
References
Algorithms and Complexity Results for the Capacitated Vertex Cover Problem
1 Introduction
2 Difficulty of the Problem
3 Treewidth
4 Exact Exponential Time Algorithms
4.1 Graphs of Bounded Degree
4.2 Graphs with Large Matchings
4.3 Instances with Capacity and Edge Restrictions
5 Conclusion
References
Comparative Expressiveness of Product Line Calculus of Communicating Systems and 1-Selecting Modal Transition Systems
1 Introduction
2 Preliminaries
2.1 Software Product Lines
2.2 1-Selecting Modal Transition Systems
2.3 Product Line Process Algebras
3 Design Decisions
4 Revisiting the Refinement Relation
4.1 New Refinement Relation
4.2 Refinement Relation Properties
5 Encoding PL-LTSs into 1MTSs
6 Related Work
7 Conclusion
References
A Hierarchy of Polynomial Kernels
1 Introduction
1.1 Overview of Our Results
1.2 Proof Techniques
2 Preliminaries
3 Separations
4 Lower Bounds
5 Classical Connections
References
Behavioral Strengths and Weaknesses of Various Models of Limited Automata
1 Background and Main Contributions
1.1 Limited Automata and Probabilistic Computation
1.2 Main Contributions
2 Limited Automata
2.1 Definitions of k-lpa's with the k-Limitedness Requirement
3 One-Way Pushdown Automata
3.1 One-Way Probabilistic Pushdown Automata
3.2 An Ideal Shape of 1ppda's
4 Behaviors of Limited Automata
4.1 Blank Skipping Property, Theorem1, and Proposition2
4.2 Properties of -LPFA
4.3 Power of Probabilistic Computation and Theorem4
4.4 Closure Properties of Probabilistic Classes and Proposition3
References
Locality Sensitive Hashing Schemes, Similarities, and Distortion (Invited Talk)
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken