Preface
Organization
Contents
Invited Papers
Certified Machine-Learning Models
1 Introduction
2 State of the Art
2.1 Governance of AI/ML Systems
2.2 AI Ethics by Design
2.3 Software Certification
3 Methodology
3.1 Using MAB to Test Behavior of ML Models: A Meta-Learning Process
3.2 Open Issues
3.3 Ecosystem
4 Certifying Differential Privacy
5 Conclusions
References
The Lost Recipes from the Four Schools of Amathus
1 The Four Schools of Amathus
2 Deciphering the Scrolls
3 Computational Genomics and Read-Based Haplotype Phasing
4 Back to Amathus
References
Sharing Energy for Optimal Edge Performance
1 Introduction
2 EPN and Its G-Network Representation
2.1 The G-Network Model
3 The EPN System
3.1 Cost Function, Parameters and Optimization
3.2 An Example
4 Conclusions
References
Foundations of Computer Science – Regular Papers
A Characterization of the Context-Free Languages by Stateless Ordered Restart-Delete Automata
1 Introduction
2 The Stateless Ordered Restart-Delete Automaton
3 Swift Stl-ORD-Automata Only Accept Context-Free Languages
4 Each Context-Free Language Is Accepted by a Swift-ORD-Automaton
5 Conclusion
References
A Constructive Arboricity Approximation Scheme
1 Introduction
2 Paper Outline and Contributions
3 Related Work
4 Notation and Preliminaries
5 The Surplus Graph
6 Exchanging Edges on Cycles
7 Finding the Exchange Edge Fast
8 (Near-)Exact Arboricity Algorithms
9 Conclusion and Outlook
References
A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity
1 Introduction
2 Graph Model and Game Rules
3 Determining the Winner of a Game of EPCR
3.1 Transformation
3.2 Proof of Theorem 1
4 An Upper Bound on the Length Required to Ensure an Edge-Periodic Cycle Is Robber-Win
5 Conclusion
References
Approximating Shortest Connected Graph Transformation for Trees
1 Introduction
2 Preliminaries
2.1 Symmetric Difference
2.2 Basic Facts Concerning Flips
3 Upper Bound
4 Discussion on the Tightness of the Lower Bound
References
Approximating Weighted Completion Time for Order Scheduling with Setup Times
1 Introduction
1.1 Contribution and Results
2 Model
3 Related Work
4 The One-Time Setup Problem
4.1 Transforming One-Time Setup Solutions
5 Approximations for Constant Number of Families
5.1 Series Parallel Digraph and Lawler's Algorithm
5.2 Simple Local Search Algorithm
6 Arbitrary Number of Families
6.1 Approximation Algorithm
6.2 Lower Bound on the Approximability
7 Future Work
References
Bounds for the Number of Tests in Non-adaptive Randomized Algorithms for Group Testing
1 Introduction
1.1 Old and New Results
2 The RID Model
3 The RrSD Model
4 The RsSD Model
5 Random Uniform Transversal Design Model
References
Burning Two Worlds
1 Introduction
2 Dense Graphs
3 Graphs of Small Pathlength or Treelength
3.1 Preliminaries
3.2 Burning Graphs of Small Pathlength
3.3 Burning Graphs of Small Treelength
References
Faster STR-EC-LCS Computation
1 Introduction
2 Preliminaries
2.1 Strings
2.2 STR-EC-LCS
3 Dynamic Programming Solution for the STR-EC-LCS Problem
3.1 Solution for LCS by Nakatsu et al.
3.2 Solution for STR-EC-LCS by Wang et al.
3.3 Our Solution for STR-EC-LCS
4 Algorithm
References
Kernels of Sub-classes of Context-Free Languages
1 Introduction
2 Preliminaries
3 Uniqueness of Kernels
4 Union of Kernels
5 Intersection of Kernels
6 Untouched Questions
References
Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
1 Introduction
2 Preliminaries
3 Combinatorial Results on MUSs in a Sliding Window
3.1 Changes to MUSs When Appending a Character to the Right
3.2 Changes to MUSs When Deleting the Leftmost Character
4 Algorithm for Computing MUSs in a Sliding Window
4.1 Updating a Suffix Tree and Three Loci in a Suffix Tree
4.2 Computing sqpi-1,j
4.3 Detecting MUSs to Be Added/Deleted
5 Combinatorial Results on MAWs in a Sliding Window
5.1 Changes to MAWs When Appending Character to the Right
5.2 Changes to MAWs When Deleting the Leftmost Character
5.3 Total Changes of MAWs When Sliding the Window on a String
References
On Synthesis of Specifications with Arithmetic
1 Introduction
2 Preliminaries
3 Different Levels of Nondeterminism in NLWAs
4 Synthesis
4.1 The Synthesis Game
4.2 Solving the Synthesis Game
References
On the Average State Complexity of Partial Derivative Transducers
1 Introduction
2 Preliminares
3 2D Expressions
4 The Analytic Combinatorics Framework
5 Average Descriptional Complexity Results
5.1 Average State Complexity of TPD for 2D-RE
5.2 Average State Complexity of TPD for Pairs of REs
6 Conclusions
References
On the Difference Between Finite-State and Pushdown Depth
1 Introduction
2 Preliminaries
3 Models of Computation
3.1 Finite-State Transducers
3.2 Pushdown Compressors
4 Pushdown Depth
5 Finite-State Depth
5.1 Separation from ILPDC-depth
6 Final Remarks
References
Online Scheduling with Machine Cost and a Quadratic Objective Function
1 Introduction
2 Preliminaries
3 Lower Bound
4 Algorithm
4.1 Description
4.2 Properties of the Relaxed Optimum and Algorithm ALG
4.3 Modifying the Two Schedules
4.4 Competitivness
References
Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching
1 Introduction
2 Preliminaries
3 Parallel Duel-and-Sweep Algorithm for the OPPM Problem
3.1 Pattern Preprocessing
3.2 Pattern Searching
4 Discussion
References
Parameterized Complexity of Synthesizing b-Bounded (m,n)-T-Systems
1 Introduction
2 Preliminaries
3 W[1]-Hardness Parameterized by m+n
3.1 The Proof of Lemma 2.[lem:if]1
3.2 The Proof of Lemma 2.[lem:onlyspsif]2
4 Conclusion
References
Parameterized Dynamic Variants of Red-Blue Dominating Set
1 Introduction
2 Complexity of Dynamic Red Blue Dominating Set
3 The Partial Dynamic RBDS Set Problem
4 Concluding Remarks
References
Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs
1 Introduction
2 Structural Graph Parameters
3 A Kernel for the Number of Edges with Rare Colors
4 Parameterization by Color Subsets
4.1 Number of Path-Frequent Colors
4.2 Number of Colors in at Least Three Conflicts
4.3 Parameter Intersections
References
Simple Distributed Spanners in Dense Congest Networks
1 Introduction and Related Work
1.1 On Diversity and Neighborhood Independence
1.2 Quick Review of Our Results
1.3 Related Work
2 Preliminaries
3 Spanning Graphs with Bounded Neighborhood Independence in the CONGEST Model
4 A Small Size Small Stretch Spanner in Bounded Diversity Graphs
5 Conclusion
References
The Order Type of Scattered Context-Free Orderings of Rank One Is Computable
1 Introduction
2 Notation
3 Limits of Languages
3.1 Limits in General
3.2 Finitely Many Limits
4 Conclusion
References
Up-to Techniques for Branching Bisimilarity
1 Introduction
2 Preliminaries
3 The Abstract Framework for Bisimulations
4 Branching Bisimilarity: Expansion and Context
5 Respectfulness of Up-to Context: Coalgebraic Approach
5.1 Abstract GSOS Specifications and Their Models
5.2 Respectfulness of Contextual Closure
5.3 Application to Weak Similarity
6 Conclusion and Future Work
References
Foundations of Data Science and Engineering – Regular Papers
Crowd Detection for Drone Safe Landing Through Fully-Convolutional Neural Networks
1 Introduction
2 Related Work
3 Proposed Approach
4 Experiment
4.1 Dataset Preparation
4.2 Experimental Results
5 Conclusion
References
Explaining Single Predictions: A Faster Method
1 Introduction
2 Related Works
3 Choosing a Basic Explanation Method
3.1 Prediction Explanation Methods
4 Toward a More Efficient Method
4.1 Finding New Estimators of the Complete Influence
4.2 Evaluating the Two New Heuristics
5 Conclusion
References
Inferring Deterministic Regular Expression with Unorder
1 Introduction
2 Preliminaries
2.1 Regular Expression with Unorder
2.2 SORE, uSORE, SOA
3 Unorder-Countable Finite Automaton (uCFA)
3.1 Counter States and Update Instructions
3.2 Unorder-Countable Finite Automaton
4 Inference of uSOREs
4.1 Constructing uCFA
4.2 Counting with uCFA
4.3 Generating uSORE
5 Experiments
5.1 Generalization Abilities
5.2 Time Performance
6 Conclusion
References
POI Recommendation Based on Locality-Specific Seasonality and Long-Term Trends
1 Introduction
2 Background and Related Work
3 Method Proposal
3.1 Hybrid Matrix Factorization Model
3.2 Seasonality Pre-filtering and Modelling
3.3 Long-Term Trends Modelling
3.4 Geographical Post-filtering
4 Experimental Evaluation
4.1 Dataset
4.2 Experiment Setup
4.3 Results
5 Conclusion and Future Work
References
Selection of a Green Logical Data Warehouse Schema by Anti-monotonicity Constraint
1 Introduction
2 Background
3 The Proposed Approach: LS-Energy
4 Algorithm
5 Experimental Study
6 Conclusion
References
The HyperBagGraph DataEdron: An Enriched Browsing Experience of Datasets
1 Introduction
2 Related Work and Mathematical Background
2.1 Information Space Discovery
2.2 Co-occurrence Networks
2.3 Multisets and Hb-Graphs
3 Hb-Graph Framework
3.1 Enhancing Navigation
3.2 Facet Visualisation Hb-Graphs
3.3 Navigability Through Facets
3.4 The Case of Multiple References
3.5 The DataHbEdronA video demo is available on: https://www.infos-informatique.net.
4 Results, Evaluation and Conclusion
4.1 Use Case
4.2 Evaluation
5 Future Work and Conclusion
References
Towards the Named Entity Recognition Methods in Biomedical Field
1 Introduction
2 Related Works of Named Entity Recognition in Biomedicine
3 Natural Language Processing
4 Research Methodology and Implementation of Selected Methods
5 Results and Discussion
6 Conclusions
References
Vietnamese Punctuation Prediction Using Deep Neural Networks
1 Introduction
2 Punctuation Prediction as Sequence Tagging
2.1 Problem Formulation
2.2 Punctuation Prediction with Conditional Random Field
3 Neural Networks for Punctuation Prediction
3.1 Network Architectures
3.2 Training with Focal Loss
4 Datasets for Vietnamese Punctuation Prediction
5 Experiments
6 Conclusion and Future Work
References
Foundations of Software Engineering – Regular Papers
A Light-Weight Tool for the Self-assessment of Security Compliance in Software Development – An Industry Case
1 Introduction
2 Fundamentals and Related Work
2.1 The IEC 62443-4-1 Security Standard
2.2 The Security Standard Compliance Assessment Model - S2C-AM
2.3 Other Security Assessment Approaches
3 Security Compliance Self-assessment
4 Tool Implementation for a Self-assessment of Security Compliance
5 Preliminary Evaluation at Siemens
5.1 Design
5.2 Results
6 Conclusion
References
A Novel Hybrid Genetic Algorithm for the Two-Stage Transportation Problem with Fixed Charges Associated to the Routes
1 Introduction
2 Definition of the Two-Stage Fixed-Charges Transportation Problem
3 Description of the Hybrid Metaheuristic Algorithm
4 Computational Results
5 Conclusions
References
Do People Use Naming Conventions in SQL Programming?
1 Introduction
2 Related Work
3 Setup
3.1 Reference SQL Naming Style
3.2 Database Schemas
4 Research Questions and Answers
4.1 Is the Reference Style Followed by the Schemas?
4.2 Does the Adherence of the Schemas to the Reference Style Evolve?
4.3 Threats to Validity
5 Conclusion
References
Employing Costs in Multiagent Systems with Timed Migration and Timed Communication
1 Introduction
2 Syntax and Operational Semantics of cTiMO
3 Translating cTiMO into Weighted Timed Automata
4 Simulating cTiMO Multiagent Systems by using Uppaal
5 Conclusion and Related Work
References
Maintainability of Automatic Acceptance Tests for Web Applications—A Case Study Comparing Two Approaches to Organizing Code of Test Cases
1 Introduction
2 Case Study
2.1 Case Selection
2.2 Test Suite Implementation and Maintenance
2.3 Data Collection and Analysis
3 Results and Observations
4 Threats to Validity
5 Related Work
6 Conclusions
References
Recommending Trips in the Archipelago of Refactorings
1 Introduction
2 Related Work
3 Refactoring Trip Advisor
3.1 Modelling Refactoring Relations
3.2 Recommending Refactoring Trips
4 Validation
4.1 Fitness for Purpose
4.2 The Developers' Opinions
5 Conclusion
References
String Representations of Java Objects: An Empirical Study
1 Introduction
2 Method Outline
3 ToString Definitions
4 ToString Invocations
4.1 Explicit and Implicit Calls
4.2 Calls from Other ToStrings
4.3 Other Usage Scenarios
5 ToString Contents
5.1 Language Constructs
5.2 Reusing Superclass Implementations
5.3 Schematic Implementations
5.4 Member Variables Read
6 Threats to Validity
6.1 Construct Validity
6.2 External Validity
7 Related Work
8 Conclusion and Future Work
References
Foundations of Algorithmic Computational Biology – Regular Papers
Fast Indexes for Gapped Pattern Matching
1 Introduction
2 VLG Matching via Sorting and Scanning Suffix Array Intervals
3 Filter, Filter, Sort, Scan
4 Direct Text Checking
5 Experimental Evaluation
6 Concluding Remarks
References
Linearizing Genomes: Exact Methods and Local Search
1 Introduction
2 Notation and Problem Description
3 Related Work
4 Hardness Using PLS-Reduction
5 Exact Methods
5.1 Integer Linear Programming
5.2 Dynamic Programming on Tree Decompositions
6 Experiments
7 Conclusion
References
Scanning Phylogenetic Networks Is NP-hard
1 Introduction
2 Preliminaries
3 NP-completeness
3.1 An Adaptation of a Known NP-hardness Proof
3.2 Reducing Nice Polytomies and Leaves
References
The Maximum Equality-Free String Factorization Problem: Gaps vs. No Gaps
1 Introduction
2 Preliminaries
3 A Better FPT Algorithm for MaxEFF-S
4 A 12-Approximation Algorithm for OptGEFF-s
5 ILP Formulations for OptEFF-S and OptGEFF-S
6 Heuristic and Approximation Algorithms for OptEFF-S
6.1 Description of Greedy1
6.2 Description of Greedyk
6.3 Experimental Results
7 Conclusions and Open Problems
References
Foundations of Computer Science – Short Papers
A Calculus for Language Transformations
1 Introduction
2 A Calculus for Language Transformations
2.1 Syntax of L–Tr
2.2 Operational Semantics of L–Tr
2.3 Type System of L–Tr
3 Examples
4 Related Work
5 Conclusion
References
Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract)
1 Introduction
2 Preliminaries
3 Algorithms for the Directed Steiner Path Cover Problem
3.1 Computing the Optimal Number of Paths
3.2 Computing the Optimal Number of Steiner Vertices
3.3 Computing an Optimal Directed Steiner Path Cover
4 Conclusions
References
Counting Infinitely by Oritatami Co-transcriptional Folding
1 Introduction
2 Preliminaries
3 Folding an Infinite Binary Counter
References
On Synchronizing Tree Automata and Their Work–Optimal Parallel Run, Usable for Parallel Tree Pattern Matching
1 Introduction
2 Basic Notions
3 Synchronizing Term and k-Local DFTA
4 Parallel Run of k-local DFTA on EREW-PRAM
References
On the Hardness of Energy Minimisation for Crystal Structure Prediction
1 Introduction
2 Notation and Definitions
3 NP-Hardness for an Unbounded Number of Ion Species
4 NP-Hardness for a Bounded Number of Species
References
Practical Implementation of a Quantum Backtracking Algorithm
1 Introduction
2 Preliminaries
3 Variable Ordering Heuristics
4 Generic Implementation
4.1 How to Implement a Predicate
4.2 How to Check a Constraint
4.3 General Structure
5 Simulation Results
6 Conclusion
References
Simplified Emanation Graphs: A Sparse Plane Spanner with Steiner Points
1 Introduction
2 Simplification Method
3 Experimental Comparison
4 Discussion
References
Simultaneous FPQ-Ordering and Hybrid Planarity Testing
1 Introduction
2 Preliminaries
3 Fixedness and 1-Fixed Constrained Planarity
3.1 A New Definition of Fixedness
3.2 1-Fixed Constrained Planarity
4 Hybrid Planarity Testing Problems
References
Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium
1 Introduction
1.1 Related Work
1.2 Our Results
2 Preliminaries
2.1 Competitive Diffusion Game
2.2 Graph Classes
3 The Existence of a Nash Equilibrium
3.1 Split Graph
3.2 Block Graph
3.3 Interval Graph
4 Some Other Results
References
Foundations of Data Science and Engineering – Short Papers
Automatic Text Generation in Slovak Language
1 Introduction
2 Related Work
3 Model
4 Evaluation
4.1 Dataset
4.2 Training
4.3 Article Generation
4.4 Results
5 Conclusions and Future Work
References
Connecting Galaxies: Bridging the Gap Between Databases and Applications
1 Introduction
2 Models and Conversions
3 Implementation
3.1 Application Considerations
3.2 Database Considerations
4 Field Measurements
5 Related Work
6 Conclusion
References
GRaCe: A Relaxed Approach for Graph Query Caching
1 Introduction
2 Problem Statement and GRaCe Architecture
3 Cache Selection Algorithm
3.1 Graph Query Matching and Cache Data Structure
3.2 Selection Algorithm
4 Extending the Planner
5 Experimental Evaluation
5.1 Experimental Setup
5.2 Experimental Results
6 Concluding Remarks
References
Modelling of the Fake Posting Recognition in On-Line Media Using Machine Learning
1 Introduction
2 Fake Reviews Detection
2.1 Fake Reviews in Online Space
2.2 State of the Art
3 Used Machine Learning Methods
4 Models Building
4.1 Data Source
4.2 Data Preprocessing
5 Models Testing
6 Conclusions
References
Two-Step Memory Networks for Deep Semantic Parsing of Geometry Word Problems
1 Introduction
2 Related Work
3 Two-Step Memory Networks
3.1 Task Definition
3.2 Limitations of Existing Memory Networks
3.3 Model Formulation
4 Experiments
4.1 Unary Rule Extraction
4.2 Binary Rule Extraction
4.3 On-Demand Fact Extraction
4.4 Relation Completion
5 Conclusion and Future Work
References
Foundations of Software Engineering – Short Papers
A Case Study on a Hybrid Approach to Assessing the Maturity of Requirements Engineering Practices in Agile Projects (REMMA)
1 Introduction
2 Case Study
3 Results
4 Conclusions
References
Does Live Regression Testing Help?
1 Introduction and Related Work
2 Proposed Method
2.1 Regression Test Selection Method
2.2 Test Case Prioritization Method
3 Evaluation
3.1 Experiment Design
3.2 Evaluation Results
4 Findings and Discussion
References
Foundations of Algorithmic Computational Biology – Short Paper
Dense Subgraphs in Biological Networks
1 Introduction
1.1 Related Works
1.2 Contribution
2 Definitions
2.1 Greedy and Constrained Greedy Algorithm for Densest-Subgraph
3 A Heuristic for Top-k-Overlapping Densest Subgraphs
4 Experimental Results
5 Conclusion
References
Author Index