SOFSEM 2019: Theory and Practice of Computer Science

This work presents a new reference architecture for multi-layer autonomic systems called context-controlled autonomic controllers (ConAC). Usually, the principle of multiple system layers contradicts the principle of a global adaptation strategy, because system layers are considered to be black boxes. The presented architecture relies on an explicit context model, so a simple change of contexts can consistently vary the adaptation strategies for all layers. This reveals that explicit context modeling enables consistent meta-adaptation in multi-layer autonomic systems. The paper presents two application areas for the ConAC architecture, robotic co-working and energy-adaptive servers, but many other multi-layered system designs should benefit from it.

Suppose we have identified a set of subjects in a terrorist network suspected of organizing an attack. Which other subjects, likely to be involved, should we keep under control? Similarly, given a set of patients infected with a viral disease, which other people should we monitor? Given a set of companies trading anomalously on the stock market: is there any connection among them that could explain the anomaly? Given a set of proteins of interest, which other proteins participate in pathways with them? Given a set of users in a social network that clicked an ad, to which other users (by the principle of “homophily”) should the same ad be shown?

The term minicomplexity was first suggested in [2], as a name for the field of theory of computation which studies the size complexity of two-way finite automata, as outlined in [1]. In this talk, we discuss the motivation behind this field and enumerate some of its prominent results in their historical context. By reformulating these results, we then attempt to reveal additional structure which often passes unnoticed. The present report records the start of this attempt.

Software engineering is an applied discipline of science. Its focus on software development processes, technologies and organizations makes it broad and exciting to work with. However, it makes it also challenging to find the right research method to get the results that have impact on industrial practices and that help software organizations to provide more value to their customers. In this paper, I argue that the traditional empirical software engineering methods must be complemented with action research. In the paper, I provide an overview of the methodology of action research, briefly explain the phases and present my experiences from over a decade long applications of action research in industrial contexts. I focus on how action research helps to provide the most value to the collaborating companies, how it helps to build more robust software engineering theories and how it helps individual researchers to develop their careers. I conclude with a short description of how action research can evolve in the future.

Today’s knowledge bases (KBs) capture facts about the world’s entities, their properties, and their semantic relationships in the form of subject-predicate-object (SPO) triples. Domain-oriented KBs, such as DBpedia, Yago, Wikidata or Freebase, capture billions of facts that have been (semi-)automatically extracted from Wikipedia articles. Their commercial counterparts at Google, Bing or Baidu provide back-end support for search engines, online recommendations, and various knowledge-centric services.This invited talk provides an overview of our recent contributions—and also highlights a number of open research challenges—in the context of extracting, managing, and reasoning with large semantic KBs. Compared to domain-oriented extraction techniques, we aim to acquire facts for a much broader set of predicates. Compared to open-domain extraction methods, the SPO arguments of our facts are canonicalized, thus referring to unique entities with semantically typed predicates. A core part of our work focuses on developing scalable inference techniques for querying an uncertain KB in the form of a probabilistic database. A further, very recent research focus lies also in scaling out these techniques to a distributed setting. Here, we aim to process declarative queries, posed in either SQL or logical query languages such as Datalog, via a proprietary, asynchronous communication protocol based on the Message Passing Interface.

The sorting number of a graph with n vertices is the minimum depth of a sorting network with n inputs and n outputs that uses only the edges of the graph to perform comparisons. Many known results on sorting networks can be stated in terms of sorting numbers of different classes of graphs. In this paper we show the following general results about the sorting number of graphs. 1. Any n-vertex graph that contains a simple path of length d has a sorting network of depth $$O(n \log (n/d))$$ . 2. Any n-vertex graph with maximal degree $$\varDelta $$ has a sorting network of depth $$O(\varDelta n)$$ . We also provide several results relating the sorting number of a graph with its routing number, size of its maximum matching, and other well known graph properties. Additionally, we give some new bounds on the sorting number for some typical graphs.

The concept of Reload cost in a graph refers to the cost that occurs while traversing a vertex via two of its incident edges. This cost is uniquely determined by the colors of the two edges. This concept has various applications in transportation networks, communication networks, and energy distribution networks. Various problems using this model are defined and studied in the literature. The problem of finding a spanning tree whose diameter with respect to the reload costs is the smallest possible, the problems of finding a path, trail or walk with minimum total reload cost between two given vertices, problems about finding a proper edge coloring of a graph such that the total reload cost is minimized, the problem of finding a spanning tree such that the sum of the reload costs of all paths between all pairs of vertices is minimized, and the problem of finding a set of cycles of minimum reload cost, that cover all the vertices of a graph, are examples of such problems. In this work we focus on the last problem. Noting that a cycle cover of a graph is a 2-factor of it, we generalize the problem to that of finding an r-factor of minimum reload cost of an edge colored graph. We prove several NP-hardness results for special cases of the problem. Namely, bounded degree graphs, planar graphs, bounded total cost, and bounded number of distinct costs. For the special case of $$r=2$$ , our results imply an improved NP-hardness result. On the positive side, we present a polynomial-time solvable special case which provides a tight boundary between the polynomial and hard cases in terms of r and the maximum degree of the graph. We then investigate the parameterized complexity of the problem, prove W[1]-hardness results and present an FPT-algorithm.

Divisorial gonality and stable divisorial gonality are graph parameters, which have an origin in algebraic geometry. Divisorial gonality of a connected graph G can be defined with help of a chip firing game on G. The stable divisorial gonality of G is the minimum divisorial gonality over all subdivisions of edges of G.In this paper we prove that deciding whether a given connected graph has stable divisorial gonality at most a given integer k belongs to the class NP. Combined with the result that (stable) divisorial gonality is NP-hard by Gijswijt, we obtain that stable divisorial gonality is NP-complete. The proof consists of a partial certificate that can be verified by solving an Integer Linear Programming instance. As a corollary, we have that the number of subdivisions needed for minimum stable divisorial gonality of a graph with n vertices is bounded by $$2^{p(n)}$$ for a polynomial p.

We investigate strong Nash equilibria in the max k-cut game, where we are given an undirected edge-weighted graph together with a set $$\{1,\ldots , k\}$$ of k colors. Nodes represent players and edges capture their mutual interests. The strategy set of each player v consists of the k colors. When players select a color they induce a k-coloring or simply a coloring. Given a coloring, the utility (or payoff) of a player u is the sum of the weights of the edges $$\{u,v\}$$ incident to u, such that the color chosen by u is different from the one chosen by v. Such games form some of the basic payoff structures in game theory, model lots of real-world scenarios with selfish agents and extend or are related to several fundamental classes of games.Very little is known about the existence of strong equilibria in max k-cut games. In this paper we make some steps forward in the comprehension of it. We first show that improving deviations performed by minimal coalitions can cycle, and thus answering negatively the open problem proposed in [13]. Next, we turn our attention to unweighted graphs. We first show that any optimal coloring is a 5-SE in this case. Then, we introduce x-local strong equilibria, namely colorings that are resilient to deviations by coalitions such that the maximum distance between every pair of nodes in the coalition is at most x. We prove that 1-local strong equilibria always exist. Finally, we show the existence of strong Nash equilibria in several interesting specific scenarios.

A matched formula is a CNF formula whose incidence graph admits a matching which matches a distinct variable to every clause. We study phase transition in a context of matched formulas and their generalization of biclique satisfiable formulas. We have performed experiments to find a phase transition of property “being matched” with respect to the ratio $$m/n$$ where $$m$$ is the number of clauses and $$n$$ is the number of variables of the input formula $$\varphi $$ . We compare the results of experiments to a theoretical lower bound which was shown by Franco and Van Gelder [11]. Any matched formula is satisfiable, and it remains satisfiable even if we change polarities of any literal occurrences. Szeider [17] generalized matched formulas into two classes having the same property—var-satisfiable and biclique satisfiable formulas. A formula is biclique satisfiable if its incidence graph admits covering by pairwise disjoint bounded bicliques. Recognizing if a formula is biclique satisfiable is NP-complete. In this paper we describe a heuristic algorithm for recognizing whether a formula is biclique satisfiable and we evaluate it by experiments on random formulas. We also describe an encoding of the problem of checking whether a formula is biclique satisfiable into SAT and we use it to evaluate the performance of our heuristic.

Prefix normal words are binary words that have no factor with more 1s than the prefix of the same length. Finite prefix normal words were introduced in [Fici and Lipták, DLT 2011]. In this paper, we study infinite prefix normal words and explore their relationship to some known classes of infinite binary words. In particular, we establish a connection between prefix normal words and Sturmian words, between prefix normal words and abelian complexity, and between prefix normality and lexicographic order.

We consider the Bamboo Garden Trimming (BGT) problem introduced in [Gąsieniec et al., SOFSEM’17]. The problem is NP-hard due to its close relationship to Pinwheel scheduling. The garden with n bamboos is an analogue of a system of n machines which have to be attended (e.g., serviced) with different frequencies. During each day, bamboo $$b_i$$ grows an extra height $$h_i,$$ for $$i=1,\dots ,n$$ and, on the conclusion of the day, at most one bamboo is cut all its current height. The goal is to design a perpetual schedule of cuts to keep the height of the tallest ever bamboo as low as possible.Our contribution is twofold, and is both theoretical and experimental. In particular, we focus on understanding what we call priority schedulings, i.e. cutting strategies where priority is given to bamboos whose current height is above a threshold greater than or equal to $$H=\sum _{i=1}^n h_i$$ . Value H represents the total daily growth of the system and it is known that one cannot keep bamboos in the garden below this threshold indefinitely.We prove that for any distribution of integer growth rates $$h_1,\dots ,h_n$$ and any priority scheduling, the system stabilises in a fixed cycle of cuts. Then, we focus on the so-called $$\mathtt {ReduceMax}_{}$$ strategy, a greedy priority scheduling which each day cuts the tallest bamboo, regardless of the growth rates distribution. $$\mathtt {ReduceMax}_{}$$ is known to provide a $$O(\log n)$$ -approximation, w.r.t. the lower bound H. We prove that, if $$\mathtt {ReduceMax}_{}$$ stabilises in a round-robin type cycle, then it guarantees 2-approximation. We conjecture that $$\mathtt {ReduceMax}_{}$$ is 2-approximating for the BGT problem, hence we conduct an extended experimental evaluation, on all bounded in size integer instances of BGT, to support our conjecture and to compare $$\mathtt {ReduceMax}_{}$$ with other relevant scheduling algorithms. Our results show that $$\mathtt {ReduceMax}_{}$$ provides 2-approximation in such instances, and it always outperforms other considered strategies, even those for which better worst case approximation guarantees have been proven.

We study the problem of patrolling the nodes of a network collaboratively by a team of mobile agents, such that each node of the network is visited by at least one agent once in every I(n) time units, with the objective of minimizing the idle time I(n). While patrolling has been studied previously for static networks, we investigate the problem on dynamic networks with a fixed set of nodes, but dynamic edges. In particular, we consider 1-interval-connected ring networks and provide various patrolling algorithms for such networks, for $$k=2$$ or $$k>2$$ agents. We also show almost matching lower bounds that hold even for the best starting configurations. Thus, our algorithms achieve close to optimal idle time. Further, we show a clear separation in terms of idle time, for agents that have prior knowledge of the dynamic networks compared to agents that do not have such knowledge. This paper provides the first known results for collaborative patrolling on dynamic graphs.

The gathering of two or more agents in a graph is an important problem in the area of distributed computing and has been extensively studied especially for the fault free scenario. In this paper we consider the mobile agents gathering problem in the presence of an adversarial malicious agent which by occupying an empty node might prevent honest agents from entering this node. The honest agents move in synchronous rounds and at each round an agent can move to an adjacent node only if this node is not occupied by the malicious agent. We model the honest agents as identical finite state automata moving in an anonymous oriented grid topology and having no information about the size of the graph, while the malicious agent is assumed to be arbitrarily fast and to have full knowledge of the locations and the strategy of the honest agents at all times. The agents cannot leave messages at nodes or communicate with each-other unless they meet at a node. Previous studies consider the problem for ring networks and for asynchronous grids, where rendezvous was solved only for the special case of agents starting already in connected configurations. In this paper, we study the problem for synchronous agents in anonymous oriented grid networks for any number of agents starting in distinct locations. We first show that rendezvous is impossible for 2 agents even when the agents can see the locations of each-other at all times, while 3 agents can gather if they have global visibility. We then present a universal deterministic algorithm that solves the problem for 4 or more agents having only local visibility and constant memory, in any oriented grid with a malicious mobile adversary.

We examine a parameterized complexity class for randomized computation where only the error bound and not the full runtime is allowed to depend more than polynomially on the parameter, based on a proposal by Kwisthout in [15, 16]. We prove that this class, for which we propose the shorthand name PPPT, has a robust definition and is in fact equal to the intersection of the classes paraBPP and PP. This result is accompanied by a Cook-style proof of completeness for the corresponding promise class (under a suitable notion of reduction) for parameterized approximation versions of the inference problem in Bayesian networks, which is known to be PP-complete. With these definitions and results in place, we proceed by showing how it follows from this that derandomization is equivalent to efficient deterministic approximation methods for the inference problem. Furthermore, we observe as a straightforward application of a result due to Drucker in [8] that these problems cannot have polynomial size randomized kernels unless the polynomial hierarchy collapses to the third level. We conclude by indicating potential avenues for further exploration and application of this framework.

A matrix ins-del system is described by a set of insertion-deletion rules presented in matrix form, which demands all rules of a matrix to be applied in the given order. These systems were introduced to model very simplistic fragments of sequential programs based on insertion and deletion as elementary operations as can be found in biocomputing. We are investigating such systems with limited resources as formalized in descriptional complexity. A traditional descriptional complexity measure of such a system is its ins-del size. Summing up the according numbers, we arrive at the sum-norm. We show that matrix ins-del systems with sum-norm 4 and (i) maximum length 3 with only one of insertion or deletion being performed under a one-sided context, or (ii) maximum length 2 with both insertion and deletion being performed under a one-sided context, can describe all recursively enumerable languages. We also show that if a matrix ins-del system of size s can describe the class of linear languages $$\mathrm {LIN}$$ , then without any additional resources, matrix ins-del systems of size s also describe the regular closure of $$\mathrm {LIN}$$ .

We identify difference-bound set constraints (DBS), an analogy of difference-bound arithmetic constraints for sets. DBS can express not only set constraints but also arithmetic constraints over set elements. We integrate DBS into separation logic with linearly compositional inductive predicates, obtaining a logic thereof where set data constraints of linear data structures can be specified. We show that the satisfiability of this logic is decidable. A crucial step of the decision procedure is to compute the transitive closure of DBS-definable set relations, to capture which we propose an extension of quantified set constraints with Presburger Arithmetic (RQSPA). The satisfiability of RQSPA is then shown to be decidable by harnessing advanced automata-theoretic techniques.

We consider the problem of matching reconfiguration, where we are given two matchings $$M_s$$ and $$M_t$$ in a graph G and the goal is to determine if there exists a sequence of matchings $$M_0, M_1, \ldots , M_\ell $$ , such that $$M_0 = M_s$$ , all consecutive matchings differ by exactly two edges (specifically, any matching is obtained from the previous one by the addition and deletion of one edge), and $$M_\ell = M_t$$ . It is known that the existence of such a sequence can be determined in polynomial time [5].We extend the study of reconfiguring matchings to account for the length of the reconfiguration sequence. We show that checking if we can reconfigure $$M_s$$ to $$M_t$$ in at most $$\ell $$ steps is NP-hard, even when the graph is unweighted, bipartite, and the maximum degree is four, and the matchings $$M_s$$ and $$M_t$$ are maximum matchings. We propose two simple algorithmic approaches, one of which improves on the brute-force running time while the other is a SAT formulation that we expect will be useful in practice.

There have been many attempts to find directed graph classes with bounded directed path-width and bounded directed tree-width. Right now, the only known directed tree-width-/path-width-bounded graphs are cycle-free graphs with directed path-width and directed tree-width 0. In this paper, we introduce directed versions of cactus trees and pseudotrees and -forests and characterize them by at most three forbidden directed graph minors. Furthermore, we show that directed cactus trees and forests have a directed tree-width of at most 1 and directed pseudotrees and -forests even have a directed path-width of at most 1.

Backdoors and backbones of Boolean formulas are hidden structural properties. A natural goal, already in part realized, is that solver algorithms seek to obtain substantially better performance by exploiting these structures.However, the present paper is not intended to improve the performance of SAT solvers, but rather is a cautionary paper. In particular, the theme of this paper is that there is a potential chasm between the existence of such structures in the Boolean formula and being able to effectively exploit them. This does not mean that these structures are not useful to solvers. It does mean that one must be very careful not to assume that it is computationally easy to go from the existence of a structure to being able to get one’s hands on it and/or being able to exploit the structure.For example, in this paper we show that, under the assumption that $$\mathrm {P}\ne \mathrm {NP}$$ , there are easily recognizable families of Boolean formulas with strong backdoors that are easy to find, yet for which it is hard (in fact, NP-complete) to determine whether the formulas are satisfiable. We also show that, also under the assumption $$\mathrm {P}\ne \mathrm {NP}$$ , there are easily recognizable sets of Boolean formulas for which it is hard (in fact, NP-complete) to determine whether they have a large backbone.

We consider the point set embedding problem (PSE) for 1-, 2- and k-planar graphs where at most 1, 2, or k crossings resp. are allowed for each edge which greatly extends the well-researched class of planar graphs. For any set of n points and any given embedded graph that belongs to one of the above graph classes, we compute a 1-to-1 mapping of the vertices to the points such that the edges can be routed using only a limited number of bends according to the given embedding and the sequences of crossings. Surprisingly, for the class of 1-planar graphs the same results can be achieved as the best known results for planar graphs. Additionally for k-planar graphs, the bounds are also much better than expected from the first sight.

We consider the problem of enumerating all connected induced subgraphs of order k in an undirected graph $$G=(V,E)$$ . Our main results are two enumeration algorithms with a delay of $$\mathcal {O}(k^2\varDelta )$$ where $$\varDelta $$ is the maximum degree in the input graph. This improves upon a previous delay bound [Elbassioni, JGAA 2015] for this problem. In addition, we give improved worst-case running time bounds and delay bounds for several known algorithms and perform an experimental comparison of these algorithms for $$k\le 10$$ and $$k\ge |V|-3$$ .

Classical string assembling systems form computational models that generate strings from copies out of a finite set of assembly units. The underlying mechanism is based on piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generative power of such systems is driven by the power of the matching of the two strands. Here we generalize this approach to multi-stranded systems. The generative capacities and the relative power are our main interest. In particular, we consider briefly one-stranded systems and obtain that they describe a subregular language family. Then we explore the relations with one-way multi-head finite automata and show an infinite, dense, and strict strand hierarchy. Moreover, we consider the relations with the linguistic language families of the Chomsky Hierarchy and consider the unary variants of k-stranded string assembling systems.

Cloud service providers who offer services to their users traditionally signal security of their offerings through certifications based on various certification schemes. Currently, a vast number of schemes and standards exists on one side (cloud service certifications), while another large set of security requirements stemming from internal needs or laws and regulations stand on the other side (users of cloud services). Determining whether a service with an arbitrary certificate in one country fulfills requirements imposed by the user in another country is a difficult task and therefore a project (EU-SEC) was started focusing on allowing cross-border usage of cloud services. In this paper, we propose automated comparison of cloud service security certification schemes and, subsequently, security of cloud services certified using these schemes. In the presented method, we map requirements in schemes, standards, laws, and regulations into a proposed cloud service security ontology. Due to the free-form text nature of these items, we also describe a supporting method for semi-automated conversion of free text into this ontology using natural language processing. The requirements described in ontology format are then easily compared against each other. We also describe an implementation of a prototype system supporting the conversion and comparison with preliminary results on describing and comparing two well-known schemes.

GF(2)-grammars, recently introduced by Bakinova et al. (“ Formal languages over GF(2) ”, LATA 2018), are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: $$K \odot L$$ is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L. This paper establishes several results on the family of languages defined by these grammars. Over the unary alphabet, GF(2)-grammars define exactly the 2-automatic sets. No language of the form $$\{a^n b^{f(n)} \,\mid \, n \geqslant 1\}$$ , with uniformly superlinear f, can be described by any GF(2)-grammar. The family is not closed under union, intersection, classical concatenation and Kleene star, non-erasing homomorphisms. On the other hand, this family is closed under injective nondeterministic finite transductions, and contains a hardest language under reductions by homomorphisms.

An adequate combination of verification and validation (V&V) methods is important to improve software quality control throughout the development process and to reduce costs. However, to find an appropriate set of V&V methods that properly addresses the desired quality characteristics of a given project is a NP-hard problem. In this paper, we present a novel approach that combines V&V methods efficiently in order to properly cover a set of quality characteristics. We modelled the problem using a bipartite graph to represent the relationships between V&V methods and quality characteristics. Then we interpreted our problem as the Set Cover problem. Although Set Cover is considered hard to be solved, through the theoretical framework of Parameterized Complexity we propose an FPT-Algorithm (fixed-parameter tractable algorithm) that effectively solves the problem, considering the number of quality characteristics to be covered as a fixed parameter. We conclude that the proposed algorithm enables combining V&V methods in a scalable and efficient way, representing a valuable contribution to the community.

The notion of robustness in the context of committee elections was introduced by Bredereck et al. [SAGT 2018] [2] to capture the impact of small changes in the input preference orders, depending on the voting rules used. They show that for certain voting rules, such as Chamberlin-Courant, checking if an election instance is robust, even to the extent of a small constant, is computationally hard. More specifically, it is NP-hard to determine if one swap in any of the votes can change the set of winning committees with respect to the Chamberlin-Courant voting rule. Further, the problem is also $$\mathsf {W[1]}$$ -hard when parameterized by the size of the committee, k. We complement this result by suggesting an algorithm that is in $$\mathsf {XP}$$ with respect to k. We also show that on nearly-structured profiles, the problem of robustness remains NP-hard. We also address the case of approval ballots, where we show a hardness result analogous to the one established in [2] about rankings and again demonstrate an $$\mathsf {XP}$$ algorithm.

The mathematical analysis of robustness and error-tolerance of complex networks has been in the center of research interest. On the other hand, little work has been done when the attack-tolerance of the vertices or edges are not independent but certain classes of vertices or edges share a mutual vulnerability. In this study, we consider a graph and we assign colors to the vertices or edges, where the color-classes correspond to the shared vulnerabilities. An important problem is to find robustly connected vertex sets: nodes that remain connected to each other by paths providing any type of error (i.e. erasing any vertices or edges of the given color). This is also known as color-avoiding percolation.In this paper, we study various possible modeling approaches of shared vulnerabilities, we analyze the computational complexity of finding the robustly (color-avoiding) connected components. We find that the presented approaches differ significantly regarding their complexity.

The concept of lackadaisical quantum walk – quantum walk with self loops – was first introduced for discrete-time quantum walk on one-dimensional line [8]. Later it was successfully applied to improve the running time of the spacial search on two-dimensional grid [16].In this paper we study search by lackadaisical quantum walk on the two-dimensional grid with multiple marked vertices. First, we show that the lackadaisical quantum walk, similarly to the regular (non-lackadaisical) quantum walk, has exceptional configuration, i.e. placements of marked vertices for which the walk has no speed-up over the classical exhaustive search. Next, we demonstrate that the weight of the self-loop suggested in [16] is not optimal for multiple marked vertices. And, last, we show how to adjust the weight of the self-loop to overcome the aforementioned problem.

Given a graph, an L(2, 1)-labeling of the graph is an assignment $$\ell $$ from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), $$|\ell (u) - \ell (v)| \ge 2$$ if u and v are adjacent, and $$\ell (u) \ne \ell (v)$$ if u and v are at distance 2. The L(2, 1)-labeling problem is to minimize the span of $$\ell $$ (i.e., $$\max _{u \in V}(\ell (u)) - \min _{u \in V}(\ell (u)) + 1$$ ). In this paper, we propose a new polynomial-time 116/13-approximation algorithm for L(2, 1)-labeling of unit disk graphs. This improves the previously best known ratio 12.

A group of mobile agents is given a task to explore an edge-weighted graph G, i.e., every vertex of G has to be visited by at least one agent. There is no centralized unit to coordinate their actions, but they can freely communicate with each other. The goal is to construct a deterministic strategy which allows agents to complete their task optimally. In this paper we are interested in a cost-optimal strategy, where the cost is understood as the total distance traversed by agents coupled with the cost of invoking them. Two graph classes are analyzed, rings and trees, in the off-line and on-line setting, i.e., when a structure of a graph is known and not known to agents in advance. We present algorithms that compute the optimal solutions for a given ring and tree of order n, in O(n) time units. For rings in the on-line setting, we give the 2-competitive algorithm and prove the lower bound of 3/2 for the competitive ratio for any on-line strategy. For every strategy for trees in the on-line setting, we prove the competitive ratio to be no less than 2, which can be achieved by the DFS algorithm.

Finite-state acceptors are studied that have two heads that read the input from opposite sides. In addition, a set of translucent letters is associated with each state. It is shown that these two-head automata are strictly more expressive than the model with a single head, but that they still only accept languages that have a semi-linear Parikh image. In fact, we obtain a characterization for the class of linear context-free trace languages in terms of a specific class of two-head finite-state acceptors with translucent letters.

The null-type is a major source of faults in Java programs, and its overuse has a severe impact on software maintenance. Unfortunately traditional mutation testing operators do not cover null-type faults by default, hence cannot be used as a preventive measure. We address this problem by designing four new mutation operators which model null-type faults explicitly. We show how these mutation operators are capable of revealing the missing tests, and we demonstrate that these mutation operators are useful in practice. For the latter, we analyze the test suites of 15 open-source projects to describe the trade-offs related to the adoption of these operators to strengthen the test suite.

Machine learning is an increasingly important approach to Natural Language Processing. Most languages however do not possess enough data to fully utilize it. When dealing with such languages it is important to use as much auxiliary data as possible. In this work we propose a combination of multitask and multilingual learning. When learning a new task we use data from other tasks and other languages at the same time. We evaluate our approach with a neural network based model that can solve two tasks – part-of-speech tagging and named entity recognition – with four different languages at the same time. Parameters of this model are partially shared across all data and partially they are specific for individual tasks and/or languages. Preliminary experiments show that this approach has its merits as we were able to beat baseline solutions that do not combine data from all the available sources.

The state complexity of simulating 1NFA by 2DFA is a long-standing open question, which is of particular interest also due to its connection to the DLOG vs. NLOG problem for Turing machines.What makes proving lower bounds on the size of deterministic two-way automata particularly hard is the fact that one has to consider any automaton, and unlike the designer, one does not have any meaning of the states at hand. This motivates the notion of logical automata whose states are annotated by formulas representing the meaning of a state.In the paper at hand, we first introduce the notion of logical automata and present a general approach to proving lower bounds on the number of states of logical automata. We then apply this approach to derive an exponential lower bound on the size of logical automata over formulas with a restricted set of atomic predicates. Finally, we complement the lower bound with an (also exponential) upper bound.

Root Cause Analysis for anomalies is challenging because of the trade-off between the accuracy and its explanatory friendliness, required for industrial applications. In this paper we propose a framework for simple and friendly RCA within the Bayesian regime under certain restrictions (namely that Hessian at the mode is diagonal, in this work referred to as separability) imposed on the predictive posterior. Within this framework anomalies can be decomposed into independent dimensions which greatly simplifies readability and interpretability.We show that the separability assumption is satisfied for important base models, including Multinomial, Dirichlet-Multinomial and Naive Bayes. To demonstrate the usefulness of the framework, we embed it into the Bayesian Net and validate on web server error logs (real world data set).

We study the capacitated vertex cover problem (CVC). In this natural extension to the vertex cover problem, each vertex has a predefined capacity which indicates the total amount of edges that it can cover. In this paper, we study the complexity of the CVC problem. We give NP-completeness proofs for the problem on modular graphs, tree-convex graphs, and planar bipartite graphs of maximum degree three. For the first two graph classes, we prove that no subexponential-time algorithm exist for CVC unless the ETH fails.Furthermore, we introduce a series of exact exponential-time algorithms which solve the CVC problem on several graph classes in $$\mathcal {O}((2 - \epsilon )^n)$$ time, for some $$\epsilon > 0$$ . Amongst these graph classes are, graphs of maximum degree three, other degree-bounded graphs, regular graphs, graphs with large matchings, c-sparse graphs, and c-dense graphs. To obtain these results, we introduce an FPT treewidth algorithm which runs in $$\mathcal {O}^*((k + 1)^{tw})$$ or $$\mathcal {O}^*(k^k)$$ time, where k is the solution size and tw the treewidth, improving an earlier algorithm from Dom et al.

Product line calculus of communicating systems (PL-CCSs) is a process calculus proposed to model the behavior of software product lines. Modal transition systems (MTSs) are also used to model variability in behavioral models. MTSs are known to be strictly less expressive than PL-CCS. In this paper, we show that the extension of MTSs with hyper transitions by Fecher and Schmidt, called 1-selecting modal transition systems (1MTSs), closes this expressiveness gap. To this end, we propose a novel notion of refinement for 1MTSs that makes them more suitable for specifying variability for software product lines and prove its various essential properties.

In parameterized algorithmics the process of kernelization is defined as a polynomial time algorithm that transforms the instance of a given problem to an equivalent instance of a size that is limited by a function of the parameter. As, afterwards, this smaller instance can then be solved to find an answer to the original question, kernelization is often presented as a form of preprocessing. A natural generalization of kernelization is the process that allows for a number of smaller instances to be produced to provide an answer to the original problem, possibly also using negation. This generalization is called Turing kernelization. Immediately, questions of equivalence occur or, when is one form possible and not the other. These have been long standing open problems in parameterized complexity. In the present paper, we answer many of these. In particular we show that Turing kernelizations differ not only from regular kernelization, but also from intermediate forms as truth-table kernelizations. We achieve absolute results by diagonalizations and also results on natural problems depending on widely accepted complexity theoretic assumptions. In particular, we improve on known lower bounds for the kernel size of compositional problems using these assumptions.

We examine the behaviors of various models of k-limited automata, which naturally extend Hibbard’s [Inf. Control, vol. 11, pp. 196–238, 1967] scan limited automata, each of which is a linear-bounded automaton satisfying the k-limitedness requirement that the content of each tape cell should be modified only during the first k visits of a tape head. One central model is k-limited probabilistic automaton (k-lpa), which accepts an input exactly when its accepting states are reachable from its initial state with probability more than 1/2. We further study the behaviors of one-sided-error and bounded-error variants of such k-lpa’s as well as deterministic and nondeterministic models. We discuss fundamental properties of those machine models and obtain inclusions and separations among language families induced by these machine models. In due course, we study special features—the blank skipping property and the closure under reversal—which are keys to the robustness of k-lpa’s.