In this paper, we study the task of enumerating (and counting) locally and globally minimal defensive alliances in graphs. We consider general graphs as well as special graph classes, like trees, bipartite graphs, and split graphs. From an input-sensitive perspective, our presented algorithms are mostly optimal, meaning that their running times (neglecting polynomial factors) match concrete families of graphs that contain that many minimal alliances.

The concept of Roman domination has recently been studied concerning enumerating and counting in F. N. Abu-Khzam et al. (WG 2022). More technically speaking, a function that assigns 0,1,2 to the vertices of an undirected graph is called a Roman dominating function if each vertex assigned zero has a neighbor assigned two. Such a function is called minimal if decreasing any assignment to any vertex would yield a function that is no longer a Roman dominating function. It has been shown that minimal Roman dominating functions can be enumerated with polynomial delay, i.e., between any two outputs of a solution, no more than polynomial time will elapse. This contrasts what is known about minimal dominating sets, where the question whether or not these can be enumerated with polynomial delay is open for more than 40 years. This makes the concept of Roman domination rather special and interesting among the many variants of domination problems studied in the literature, as it has been shown for several of these variants that the question of enumerating minimal solutions is tightly linked to that of enumerating minimal dominating sets, see M. Kanté et al. in SIAM J. Disc. Math., 2014. The running time of the mentioned enumeration algorithm for minimal Roman dominating functions (Abu-Khzam et al., WG 2022) could be estimated as 𝒪(1.9332ⁿ) on general graphs of order n. Here, we focus on special graph classes, as has been also done for enumerating minimal dominating sets before. More specifically, for chordal graphs, we present an enumeration algorithm running in time 𝒪(1.8940ⁿ). It is unknown if this gives a tight bound on the maximum number of minimal Roman dominating functions in chordal graphs. For interval graphs, we can lower this time bound further to 𝒪(1.7321ⁿ), which also matches the known lower bound concerning the maximum number of minimal Roman dominating functions. We can also provide a matching lower and upper bound for forests, which is (incidentally) the same, namely 𝒪^*(√3ⁿ). Furthermore, we present an optimal enumeration algorithm running in time 𝒪^*(∛3ⁿ) for split graphs and for cobipartite graphs, i.e., we can also give a matching lower bound example for these graph classes. Hence, our enumeration algorithms for interval graphs, forests, split graphs and cobipartite graphs are all optimal. The importance of our results stems from the fact that, for other types of domination problems, optimal enumeration algorithms are not always found. Interestingly, we use a different form of analysis for the running times of our different algorithms, and the branchings had to be tailored and tweaked to obtain the intended optimality results. Our Roman dominating functions enumeration algorithm for trees and forests is distinctively different from the one for minimal dominating sets by Rote (SODA 2019).Our approach also allows to give concrete formulas for counting minimal Roman dominating functions on more concrete graph families like paths.

The concept of LL( k ) context-free grammars is extended to cooperating distributed (CD) grammar systems working in the = m -mode of derivation in a consistent way. Namely, every LL( k ) context-free language can be generated by an LL( k ) CD grammar system. Further fundamental properties of languages generated by LL( k ) CD grammar systems are proved, for instance their unambiguity and the capability of LL( k ) CD grammar systems to describe typical non-context-free languages, including even a non-semilinear language. Most importantly, a parsing algorithm with strictly sub-quadratic time complexity is presented for LL( k ) CD grammar systems.

The analysis of social networks and community detection is a central theme in Artificial Intelligence. One line of research deals with finding groups of agents that could work together to achieve a certain goal. To this end, different notions of so-called clusters or communities have been introduced in the literature of graphs and networks. Among these, a defensive alliance is a kind of quantitative group structure. However, all studies on alliances so far have ignored one aspect that is central to the formation of alliances on a very intuitive level, assuming that the agents are preconditioned concerning their attitude towards other agents: they prefer to be in some group (or in an alliance) together with the agents they like, so that they are happy to help each other towards their common aim, possibly then working against the agents outside of their group that they dislike. Signed networks were introduced in the psychology literature to model liking and disliking between agents, generalizing graphs in a natural way. Hence, we propose the novel notion of a defensive alliance in the context of signed networks. We then investigate several natural algorithmic questions related to this notion. These, and also combinatorial findings, connect our notion to that of correlation clustering, which is a well-established idea of finding groups of agents within a signed network. Also, we introduce a new structural parameter for signed graphs, the signed neighborhood diversity snd, and exhibit a snd-parameterized algorithm that finds one of the smallest defensive alliances in a signed graph.

Abstract. The question to enumerate all (inclusionwise) minimal connected dominating sets in a graph of order [Formula: see text] in time significantly less than [Formula: see text] is an open question that was asked in many places. We answer this question affirmatively, by providing an enumeration algorithm that runs in time [Formula: see text], using polynomial space only. The key to this result is the consideration of this enumeration problem on 2-degenerate graphs, which is proven to be possible in time [Formula: see text]. Apart from solving this old open question, we also show new lower bound results. More precisely, we construct a family of graphs of order [Formula: see text] with [Formula: see text] many minimal connected dominating sets, while previous examples achieved [Formula: see text]. Our example happens to yield 4-degenerate graphs. Additionally, we give lower bounds for the previously not considered classes of 2-degenerate and of 3-degenerate graphs, which are [Formula: see text] and [Formula: see text], respectively. We also address essential questions concerning output-sensitive enumeration. Namely, we give reasons why our algorithm cannot be turned into an enumeration algorithm that guarantees polynomial delay without much effort. More precisely, we prove that it is NP -complete to decide, given a graph [Formula: see text] and a vertex set [Formula: see text], if there exists a minimal connected dominating set [Formula: see text] with [Formula: see text], even if [Formula: see text] is known to be 2-degenerate. Our reduction also shows that even any subexponential delay is not easy to achieve for enumerating minimal connected dominating sets. Another reduction shows that no FPT -algorithms can be expected for this extension problem concerning minimal connected dominating sets, parameterized by [Formula: see text]. This also adds one more problem to the still rather few natural parameterized problems that are complete for the parameterized complexity class W [3]. We also relate our enumeration problem to the famous Hitting Set Transversal problem, a problem open for more than four decades, which can be phrased in our context as the question to enumerate all minimal dominating sets of a graph with polynomial delay, by showing that a polynomial-delay enumeration algorithm for minimal connected dominating sets implies an affirmative algorithmic (polynomial-delay) solution to the Hitting Set Transversal problem.

International audience

Abstract Roman domination is one of the many variants of domination that keeps most of the complexity features of the classical domination problem. We prove that Roman domination behaves differently in two aspects: enumeration and extension. We develop non-trivial enumeration algorithms for minimal Roman dominating functions with polynomial delay and polynomial space. Recall that the existence of a similar enumeration result for minimal dominating sets is open for decades. Our result is based on a polynomial-time algorithm for Extension Roman Domination : Given a graph $$G=(V,E)$$ G = ( V , E ) and a function $$f:V\rightarrow \{0,1,2\}$$ f : V → { 0 , 1 , 2 } , is there a minimal Roman dominating function $$\tilde{f}$$ f ~ with $$f\le \tilde{f}$$ f ≤ f ~ ? Here, $$\le $$ ≤ lifts $$0< 1< 2$$ 0 < 1 < 2 pointwise; minimality is understood in this order. Our enumeration algorithm is also analyzed from an input-sensitive viewpoint, leading to a run-time estimate of $$\mathcal {O}(1.9332^n)$$ O ( 1 . 9332 n ) for graphs of order n ; this is complemented by a lower bound example of $$\Omega (1.7441^n)$$ Ω ( 1 . 7441 n ) .

Matrix grammars are one of the first approaches ever proposed in regulated rewriting, prescribing that rules have to be applied in a certain order. In traditional regulated rewriting, the most interesting case shows up when all rules are context-free. Typical descriptional complexity measures incorporate the number of nonterminals or the length, i.e., the number of rules per matrix. When viewing matrices as program fragments, it becomes natural to consider additional applicability conditions for such matrices. Here, we focus on forbidding sets, i.e., a matrix is applicable to a sentential form w only if none of the words in its forbidding set occurs as a subword in w. This gives rise to further natural descriptional complexity measures: How long could words in forbidding sets be? How many words could be in any forbidding set? How many matrices contain non-empty forbidding contexts? As context-free grammars with forbidding sets are known as generalized forbidding grammars, we call this variant of matrix grammars also generalized forbidding. In this paper, we attempt to answer the four questions above while studying the computational completeness of generalized forbidding matrix grammars. In the course of our studies, we also define several new normal forms for type-0 grammars that might be of independent interest.

A central computational problem in the realm of automata theory is the problem of determining whether a finite automaton A has a synchronizing word. This problem has found applications in a variety of subfields of artificial intelligence, including planning, robotics, and multi-agent systems. In this work, we study this problem within the framework of diversity of solutions, an up-and-coming trend in the field of artificial intelligence where the goal is to compute a set of solutions that are sufficiently distinct from one another. We define a notion of diversity of solutions that is suitable for contexts were solutions are strings that may have distinct lengths. Using our notion of diversity, we show that for each fixed r ∈ N, each fixed finite automaton A, and each finite automaton B given at the input, the problem of determining the existence of a diverse set {w1,w2, . . . ,wr} ⊆ L(B) of words that are synchronizing for A can be solved in polynomial time. Finally, we generalize this result to the realm of conformant planning, where the goal is to devise plans that achieve a goal irrespectively of initial conditions and of nondeterminism that may occur during their execution.

Abstract Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard, which settles an open question.

Abstract A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider combinatorial questions like the minimum number of isolated vertices that need to be added to a given graph to make it a sum graph. In this paper, we initiate the study of sum graphs from the viewpoint of computational complexity. Notice that every n-vertex sum graph can be represented by a sorted list of n positive integers where edge queries can be answered in $$\mathscr {O}(\log n)$$ O ( log n ) time. Therefore, upper-bounding the numbers used as vertex labels also upper-bounds the space complexity of storing the graph in the database. We show that every n-vertex, m-edge, d-degenerate graph can be made a sum graph by adding at most m isolated vertices to it, such that the largest numbers used as vertex labels grows as $$\mathscr {O}(n^2d)$$ O ( n 2 d ) . This enables us to store the graph using $$\mathscr {O}(m\log n)$$ O ( m log n ) bits of memory. For sparse graphs (graphs with $$\mathscr {O}(n)$$ O ( n ) edges), this matches the trivial lower bound of $$\Omega (n\log n)$$ Ω ( n log n ) . As planar graphs and forests have constant degeneracy, our result implies an upper bound of $$\mathscr {O}(n^2)$$ O ( n 2 ) on their label numbers. The previously best known upper bound on the numbers needed for labelling general graphs with the minimum number of isolated vertices was $$\mathscr {O}(4^n)$$ O ( 4 n ) , due to Kratochvíl, Miller & Nguyen (2001). Furthermore, their proof was existential, whereas our labelling can be constructed in polynomial time.

We consider the unlabeled motion-planning problem of $m$ unit-disc robots moving in a simple polygonal workspace of $n$ edges. The goal is to find a motion plan that moves the robots to a given set of $m$ target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end. If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time $O(n \log n + mn + m^2)$ if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance $4$ apart, any two target positions are at least distance $4$ apart, and any pair of a start and a target positions is at least distance $3$ apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary.

The question to enumerate all (inclusion-wise) minimal connected dominating sets in a graph of order n in time significantly less than 2ⁿ is an open question that was asked in many places. We answer this question affirmatively, by providing an enumeration algorithm that runs in time 𝒪(1.9896ⁿ), using polynomial space only. The key to this result is the consideration of this enumeration problem on 2-degenerate graphs, which is proven to be possible in time 𝒪(1.9767ⁿ). Apart from solving this old open question, we also show new lower bound results. More precisely, we construct a family of graphs of order n with Ω(1.4890ⁿ) many minimal connected dominating sets, while previous examples achieved Ω(1.4422ⁿ). Our example happens to yield 4-degenerate graphs. Additionally, we give lower bounds for the previously not considered classes of 2-degenerate and of 3-degenerate graphs, which are Ω(1.3195ⁿ) and Ω(1.4723ⁿ), respectively. We also address essential questions concerning output-sensitive enumeration. Namely, we give reasons why our algorithm cannot be turned into an enumeration algorithm that guarantees polynomial delay without much efforts. More precisely, we prove that it is NP-complete to decide, given a graph G and a vertex set U, if there exists a minimal connected dominating set D with U ⊆ D, even if G is known to be 2-degenerate. Our reduction also shows that even any subexponential delay is not easy to achieve for enumerating minimal connected dominating sets. Another reduction shows that no FPT-algorithms can be expected for this extension problem concerning minimal connected dominating sets, parameterized by |U|. This also adds one more problem to the still rather few natural parameterized problems that are complete for the class W[3]. We also relate our enumeration problem to the famous open Hitting Set Transversal problem, which can be phrased in our context as the question to enumerate all minimal dominating sets of a graph with polynomial delay by showing that a polynomial-delay enumeration algorithm for minimal connected dominating sets implies an affirmative algorithmic solution to the Hitting Set Transversal problem.

Abstract Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property $$\varPhi $$ Φ . What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there is a graph satisfying $$\varPhi $$ Φ in the family? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided by studying the syntactic monoid of the specification language L if a certain torsion condition is satisfied. This condition holds trivially if L is regular. More specifically, we use a natural binary encoding of finite graphs over a binary alphabet $$\varSigma $$ Σ , and we define a regular set $$\mathbb {G}\subseteq \varSigma ^*$$ G ⊆ Σ ∗ such that every nonempty word $$w\in \mathbb {G}$$ w ∈ G defines a finite and nonempty graph. Also, graph properties can then be syntactically defined as languages over $$\varSigma $$ Σ . Then, we ask whether the automaton $$\mathcal {A}$$ A specifies some graph satisfying a certain property $$\varPhi $$ Φ . Our structural results show that we can answer this question for all “typical” graph properties. In order to show our results, we split L into a finite union of subsets and every subset of this union defines in a natural way a single finite graph F where some edges and vertices are marked. The marked graph in turn defines an infinite graph $$F^\infty $$ F ∞ and therefore the family of finite subgraphs of $$F^\infty $$ F ∞ where F appears as an induced subgraph. This yields a geometric description of all graphs specified by L based on splitting L into finitely many pieces; then using the notion of graph retraction, we obtain an easily understandable description of the graphs in each piece.

Hamburg was the place where he used to live from his childhood onwards.There, he also obtained his doctoral degree with his dissertation entitled "Kontextfrei kontrollierte ET0L-Systeme" (engl."Context-free Controlled ET0L-Systems") in 1983, and his habilitation with the thesis "Nichtdeterministische Reduktionen und logarithmische Hierarchien" (engl."Nondeterministic Reductions and Logarithmic Hierarchies") in 1986.During his Hamburg years he visited

Abstract The concept of a synchronizing word is a very important notion in the theory of finite automata. We consider the associated decision problem to decide if a given DFA possesses a synchronizing word of length at most k, where k is the standard parameter. We show that this problem DFA-SW is equivalent to the problem Monoid Factorization introduced by Cai, Chen, Downey, and Fellows. Apart from the known $\textsf{W}[2]$ -hardness results, we show that these problems belong to $\textsf{A}[2]$ , $\textsf{W}[\textsf{P}],$ and $\textsf{WNL}$ . This indicates that DFA-SW is not complete for any of these classes, and hence, we suggest a new parameterized complexity class $\textsf{W}[\textsf{Sync}]$ as a proper home for these (and more) problems. We present quite a number of problems that belong to $\textsf{W}[\textsf{Sync}]$ or are hard or complete for this new class.

In the Intersection Non-Emptiness problem, we are given a list of finite automata $A_1,A_2,\dots,A_m$ over a common alphabet $Σ$ as input, and the goal is to determine whether some string $w\in Σ^*$ lies in the intersection of the languages accepted by the automata in the list. We analyze the complexity of the Intersection Non-Emptiness problem under the promise that all input automata accept a language in some level of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy. Automata accepting languages from the lowest levels of these hierarchies arise naturally in the context of model checking. We identify a dichotomy in the dot-depth hierarchy by showing that the problem is already NP-complete when all input automata accept languages of the levels zero or one half and already PSPACE-hard when all automata accept a language from the level one. Conversely, we identify a tetrachotomy in the Straubing-Thérien hierarchy. More precisely, we show that the problem is in AC$^0$ when restricted to level zero; complete for LOGSPACE or NLOGSPACE, depending on the input representation, when restricted to languages in the level one half; NP-complete when the input is given as DFAs accepting a language in from level one or three half; and finally, PSPACE-complete when the input automata accept languages in level two or higher. Moreover, we show that the proof technique used to show containment in NP for DFAs accepting languages in the Straubing-Thérien hierarchy levels one ore three half does not generalize to the context of NFAs. To prove this, we identify a family of languages that provide an exponential separation between the state complexity of general NFAs and that of partially ordered NFAs. To the best of our knowledge, this is the first superpolynomial separation between these two models of computation.

In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of research in artificial intelligence, called solution diversity, has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space. When combined with techniques from parameterized complexity theory, the paradigm of diversity of solutions offers a powerful algorithmic framework to address problems of practical relevance. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation, a well-studied class of problems lying in the intersection of order theory and social choice theory and also in the field of order theory itself. In particular, we show that KRA is fixed-parameter tractable with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.

In this work, we consider the following order reconfiguration problem: Given a graph G together with linear orders ω and ω' of the vertices of G, can one transform ω into ω' by a sequence of swaps of adjacent elements in such a way that at each time step the resulting linear order has cutwidth (pathwidth) at most k? We show that this problem always has an affirmative answer when the input linear orders ω and ω' have cutwidth (pathwidth) at most k/2. Using this result, we establish a connection between two apparently unrelated problems: the reachability problem for two-letter string rewriting systems and the graph isomorphism problem for graphs of bounded cutwidth. This opens an avenue for the study of the famous graph isomorphism problem using techniques from term rewriting theory.

A simple semi-conditional (SSC) grammar is a form of regulated rewriting system where the derivations are controlled either by a permitting string alone or by a forbidden string alone and this condition is specified in the rule. The maximum length i (j, resp.) of the permitting (forbidden, resp.) strings serves as a measure of descriptional complexity known as the degree of such grammars. In addition to the degree, the numbers of nonterminals and of conditional rules are also counted into the descriptional complexity measures of these grammars. We improve on some previously obtained results on the computational completeness of SSC grammars by minimizing the number of nonterminals and / or the number of conditional rules for a given degree (i, j). More specifically we prove, using a refined analysis of a normal form for type-0 grammars due to Geffert, that every recursively enumerable language is generated by an SSC grammar of (i) degree (2, 1) with eight conditional rules and nine nonterminals, (ii) degree (3, 1) with seven conditional rules and seven nonterminals (iii) degree (4, 1) with six conditional rules and seven nonterminals and (iv) degree (4, 1) with eight conditional rules and six nonterminals.

We study the computational and descriptional complexity of self-verifying pushdown automata (SVPDA) and self-verifying realtime queue automata (SVRQA). A self-verifying automaton is a nondeterministic device whose nondeterminism is symmetric in the following sense. Each computation path can give one of the answers yes, no, or do not know. For every input word, at least one computation path must give either the answer yes or no, and the answers given must not be contradictory. We show that SVPDA and SVRQA are automata characterizations of so-called complementation kernels, that is, context-free or realtime nondeterministic queue automaton languages whose complement is also context free or accepted by a realtime nondeterministic queue automaton. So, the families of languages accepted by SVPDA and SVRQA are strictly between the families of deterministic and nondeterministic languages. Closure properties and various decidability problems are considered. For example, it is shown that it is not semidecidable whether a given SVPDA or SVRQA can be made self-verifying. Moreover, we study descriptional complexity aspects of these machines. It turns out that the size trade-offs between nondeterministic and self-verifying as well as between self-verifying and deterministic automata are non-recursive. That is, one can choose an arbitrarily large recursive function f, but the gain in economy of description eventually exceeds f when changing from the former system to the latter.

Abstract In the smallest grammar problem, we are given a word w and we want to compute a preferably small context-free grammar G for the singleton language {w} (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is NP-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless P = NP. We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains NP-complete (and its optimisation version is APX-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i. e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields W[1]-hardness. Furthermore, we present an $\mathcal {O}(3^{\mid {w}\mid })$ O ( 3 ∣ w ∣ ) exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i. e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the “hierarchical depth” of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.

Abstract A matrix insertion-deletion system (or 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 matrix ins-del system is its size $$s=(k;n,i',i'';m,j',j'')$$ s = ( k ; n , i ′ , i ′ ′ ; m , j ′ , j ′ ′ ) , where the parameters from left to right represent the maximal matrix length, maximal insertion string length, maximal length of left contexts in insertion rules, maximal length of right contexts in insertion rules; the last three are deletion counterparts of the previous three parameters. We call the sum $$n+i'+i''+m+j'+j''$$ n + i ′ + i ′ ′ + m + j ′ + j ′ ′ the sum-norm of s. We show that matrix ins-del systems of sum-norm 4 and sizes (3; 1, 0, 0; 1, 2, 0), (3; 1, 0, 0; 1, 0, 2), (2; 1, 2, 0; 1, 0, 0), (2; 1, 0, 2; 1, 0, 0), and (2; 1, 1, 1; 1, 0, 0) describe the recursively enumerable languages. Moreover, matrix ins-del systems of sizes (3; 1, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), (2; 2, 1, 0; 1, 0, 0) and (2; 2, 0, 1; 1, 0, 0) can describe at least the regular closure of the linear languages. In fact, we show that if a matrix ins-del system of size s can describe the class of linear languages $$\mathrm {LIN}$$ LIN , then without any additional resources, matrix ins-del systems of size s also describe the regular closure of $$\mathrm {LIN}$$ LIN . Finally, we prove that matrix ins-del systems of sizes (2; 1, 1, 0; 1, 1, 0) and (2; 1, 0, 1; 1, 0, 1) can describe at least the regular languages.

We are studying a weighted version of a linear extension problem, given some finite partial order ρ, called Completion of an Ordering. While this problem is NP-complete, we show that it lies in FPT when parameterized by the interval width of ρ. This ordering problem can be used to model several ordering problems stemming from diverse application areas, such as graph drawing, computational social choice, or computer memory management. Each application yields a special ρ. We also relate the interval width of ρ to parameterizations such as maximum range that have been introduced earlier in these applications, sometimes improving on parameterized algorithms that have been developed for these parameterizations before. This approach also gives some practical sub-exponential time algorithms for ordering problems.

We generalize the concept of synchronizing words for finite automata, which map all states of the automata to the same state, to deterministic visibly push-down automata. Here, a synchronizing word w does not only map all states to the same state but also fulfills some conditions on the stack content of each run after reading w. We consider three types of these stack constraints: after reading w, the stack (1) is empty in each run, (2) contains the same sequence of stack symbols in each run, or (3) contains an arbitrary sequence which is independent of the other runs. We show that in contrast to general deterministic push-down automata, it is decidable for deterministic visibly push-down automata whether there exists a synchronizing word with each of these stack constraints, i.e., the problems are in EXPTIME. Under the constraint (1) the problem is even in P. For the sub-classes of deterministic very visibly push-down automata the problem is in P for all three types of constraints. We further study variants of the synchronization problem where the number of turns in the stack height behavior caused by a synchronizing word is restricted, as well as the problem of synchronizing a variant of a sequential transducer, which shows some visibly behavior, by a word that synchronizes the states and produces the same output on all runs.

The question if a deterministic finite automaton admits a software reset in the form of a so-called synchronizing word can be answered in polynomial time. In this paper, we extend this algorithmic question to deterministic automata beyond finite automata. We prove that the question of synchronizability becomes undecidable even when looking at deterministic one-counter automata. This is also true for another classical mild extension of regularity, namely that of deterministic one-turn push-down automata. However, when we combine both restrictions, we arrive at scenarios with a PSPACE-complete (and hence decidable) synchronizability problem. Likewise, we arrive at a decidable synchronizability problem for (partially) blind deterministic counter automata. There are several interpretations of what synchronizability should mean for deterministic push-down automata. This is depending on the role of the stack: should it be empty on synchronization, should it be always the same or is it arbitrary? For the automata classes studied in this paper, the complexity or decidability status of the synchronizability problem is mostly independent of this technicality, but we also discuss one class of automata where this makes a difference.

Unit square (grid) visibility graphs (USV and USGV, resp.) are described by axis-parallel visibility between unit squares placed (on integer grid coordinates) in the plane. We investigate combinatorial properties of these graph classes and the hardness of variants of the recognition problem, i.e., the problem of representing USGV with fixed visibilities within small area and, for USV, the general recognition problem.

We consider the external variant of non-isometric d-dimensional contextual array grammars with regular control together with local selectors allowing for controlling how d-dimensional arrays are evolving by adjoining rectangular (d–1)-dimensional arrays. In the 1-dimensional case, the computational power of these non-isometric contextual array grammars with regular control and local selectors equals the computational power of isometric contextual array grammars with regular control. The string images of the languages of 1-dimensional arrays generated by these contextual array grammars exactly yield the linear languages. In the more-dimensional case, non-isometric d-dimensional contextual array grammars with regular control and local selectors can simulate the computations of (d – 1)-dimensional array grammars or Turing machines. Hence, for example, the emptiness problem for non-isometric d-dimensional contextual array grammars with regular control and local selectors for d > 1 is undecidable. We also compare the computational power of all variants of non-isometric d-dimensional contextual array grammars that we introduce to each other.

We consider d -dimensional contextual array grammars and investigate their computational power when using various control mechanisms – matrices, regular control languages, and tissue P systems, which work like regular control languages, but may end up with a final check for the non-applicability of some rules. For d ≥ 2 , d -dimensional contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. The use of tissue P systems with their final non-applicability check even yields some additional computational power. In the 1-dimensional case, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages can be characterized as the family of array images of the linear languages, which for a one-letter alphabet means that it coincides with the family of regular 1-dimensional array languages.

It is shown that the shortest-grammar problem remains NP-complete if the alphabet is fixed and has a size of at least 24 (which settles an open question). On the other hand, this problem can be solved in polynomial-time, if the number of nonterminals is bounded, which is shown by encoding the problem as a problem on graphs with interval structure. Furthermore, we present an O(3n) exact exponential-time algorithm, based on dynamic programming. Similar results are also given for 1-level grammars, i.e., grammars for which only the start rule contains nonterminals on the right side (thus, investigating the impact of the "hierarchical depth" on the complexity of the shortest-grammar problem).

Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios however the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality k without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to k. Further, we derive some polynomial-time solvable cases for k = 2 with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of k.

A pattern (i. e., a string of variables and terminals) maps to a word, if this is obtained by uniformly replacing the variables by terminal words; deciding this is NP-complete. We present efficient algorithms\footnote{The computational model we use is the standard unit-cost RAM with logarithmic word size. Also, all logarithms appearing in our time complexity evaluations are in base 2.} that solve this problem for restricted classes of patterns. Furthermore, we show that it is NP-complete to decide, for a given number k and a word w, whether w can be factorised into k distinct factors; this shows that the injective version (i.e., different variables are replaced by different words) of the above matching problem is NP-complete even for very restricted cases.

Given a source string u and a target string w, to decide whether w can be obtained by applying a string morphism on u (i. e., uniformly replacing the symbols in u by strings) constitutes an NP-complete problem. For example, the target string w := baaba can be obtained from the source string u := aba, by replacing a and b in u by the strings ba and a, respectively. In this paper, we contribute to the recently started investigation of the computational complexity of the string morphism problem by studying it in the framework of parameterised complexity.

The k -Leaf Out-Branching problem is to find an out-branching, that is a rooted oriented spanning tree, with at least k leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the k -Leaf-Out-Branching problem. We give the first polynomial kernel for Rooted k -Leaf-Out-Branching, a variant of k -Leaf-Out-Branching where the root of the tree searched for is also a part of the input. Our kernel with O ( k 3 ) vertices is obtained using extremal combinatorics. For the k -Leaf-Out-Branching problem, we show that no polynomial-sized kernel is possible unless coNP is in NP/poly . However, our positive results for Rooted k -Leaf-Out-Branching immediately imply that the seemingly intractable k -Leaf-Out-Branching problem admits a data reduction to n independent polynomial-sized kernels. These two results, tractability and intractability side by side, are the first ones separating Karp kernelization from Turing kernelization . This answers affirmatively an open problem regarding “cheat kernelization” raised by Mike Fellows and Jiong Guo independently.

The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least $k$ leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the {\sc $k$-Leaf-Out-Branching} problem. We give the first polynomial kernel for {\sc Rooted $k$-Leaf-Out-Branching}, a variant of {\sc $k$-Leaf-Out-Branching} where the root of the tree searched for is also a part of the input. Our kernel has cubic size and is obtained using extremal combinatorics. For the {\sc $k$-Leaf-Out-Branching} problem, we show that no polynomial kernel is possible unless the polynomial hierarchy collapses to third level by applying a recent breakthrough result by Bodlaender et al. (ICALP 2008) in a non-trivial fashion. However, our positive results for {\sc Rooted $k$-Leaf-Out-Branching} immediately imply that the seemingly intractable {\sc $k$-Leaf-Out-Branching} problem admits a data reduction to $n$ independent $O(k^3)$ kernels. These two results, tractability and intractability side by side, are the first ones separating {\it many-to-one kernelization} from {\it Turing kernelization}. This answers affirmatively an open problem regarding ``cheat kernelization'' raised by Mike Fellows and Jiong Guo independently.

We consider the construction of finite automata from their corresponding regular expressions by a series of digraph-transformations along the expression\'s structure. Each intermediate graph represents an extended finite automaton accepting the same language. The character of our construction allows a fine-grained analysis of the emerging automaton\'s size, eventually leading to an optimality result.

Determining whether a parameterized problem is kernelizable and has a small kernel size has recently become one of the most interesting topics of research in the area of parameterized complexity and algorithms. Theoretically, it has been proved that a parameterized problem is kernelizable if and only if it is fixed-parameter tractable. Practically, applying a data reduction algorithm to reduce an instance of a parameterized problem to an equivalent smaller instance (i.e., a kernel) has led to very efficient algorithms and now goes hand-in-hand with the design of practical algorithms for solving $\mathcal{NP}$-hard problems. Well-known examples of such parameterized problems include the vertex cover problem, which is kernelizable to a kernel of size bounded by $2k$, and the planar dominating set problem, which is kernelizable to a kernel of size bounded by $335k$. In this paper we develop new techniques to derive upper and lower bounds on the kernel size for certain parameterized problems. In terms of our lower bound results, we show, for example, that unless $\mathcal{P} = \mathcal{NP}$, planar vertex cover does not have a problem kernel of size smaller than $4k/3$, and planar independent set and planar dominating set do not have kernels of size smaller than $2k$. In terms of our upper bound results, we further reduce the upper bound on the kernel size for the planar dominating set problem to $67 k$, improving significantly the $335 k$ previous upper bound given by Alber, Fellows, and Niedermeier [J. ACM, 51 (2004), pp. 363–384]. This latter result is obtained by introducing a new set of reduction and coloring rules, which allows the derivation of nice combinatorial properties in the kernelized graph leading to a tighter bound on the size of the kernel. The paper also shows how this improved upper bound yields a simple and competitive algorithm for the planar dominating set problem.

A bipartite graph is biplanar if the vertices can be placed on two parallel lines in the plane such that there are no edge crossings when edges are drawn as straight-line segments. We study two problems: Improving on earlier works of Dujmović et al. [4], we solve the 2-Layer Planarization problem in $\mathcal{O}(k^{2}\cdot 5.1926^{k} +|G|)$ time and the 1-Layer Planarization problem in $\mathcal{O}(k^{3} \cdot 2.5616^{k} + |G|^{2})$ time. Moreover, we derive a small problem kernel for 1-Layer Planarization.

We show how k-grams can be used to extend classes of terminal distinguishable right-liner languages (k-TDRL). Moreover, we present an efficient identification algorithm for k-TDRL languages. Our approach not only generalizes the class TDRL, but also the k-testable languages, as well as the k-reversible languages.

We consider pure Lindenmayer systems, more precisely, 0L and T0L systems as language accepting devices and compare them to their generating counterparts. Accepting Lindenmayer systems can be seen as systems of inverse finite substitutions which are iteratively applied over a free monoid. Hereby, we investigate the deterministic case in detail, comparing several different concepts of determinism in such systems. Whereas in the usual generating case these concepts trivially are equally powerful, the structure of families of accepted languages is much richer. In passing, the case of unary Lindenmayer systems is investigated.

In this paper, we emphasize the differences of grammar families and their properties versus language families and their properties. To this end, we investigate grammar families from an abstract standpoint, developping a new framework of reasoning. In particular when considering decidability questions, special care must be taken. We illustrate this by inspecting some theorems and their proofs in the field of regulated rewriting. As an exercise, we show that there is no ‘effective’ grammatical characterization of the family of recursive languages.