Search

Traditionally, finite automata theory has been used as a framework for the representation of possibly infinite sets of strings. In this work, we introduce the notion of second-order finite automata, a formalism that combines finite automata with ordered decision diagrams, with the aim of representing possibly infinite sets of sets of strings. Our main result states that second-order finite automata can be canonized with respect to the second-order languages they represent. Using this canonization result, we show that sets of sets of strings represented by second-order finite automata are closed under the usual Boolean operations, such as union, intersection, difference and even under a suitable notion of complementation. Additionally, emptiness of intersection and inclusion are decidable. We provide two algorithmic applications for second-order automata. First, we show that several width/size minimization problems for deterministic and nondeterministic ODDs are solvable in fixed-parameter tractable time when parameterized by the width of the input ODD. In particular, our results imply FPT algorithms for corresponding width/size minimization problems for ordered binary decision diagrams (OBDDs) with a fixed variable ordering. Previously, only algorithms that take exponential time in the size of the input OBDD were known for width minimization, even for OBDDs of constant width. Second, we show that for each k and w one can count the number of distinct functions computable by ODDs of width at most w and length k in time h(|Σ|,w) ⋅ kO(1), for a suitable h : ℕ × ℕ → ℕ . This improves exponentially on the time necessary to explicitly enumerate all such functions, which is exponential in both the width parameter w and in the length k of the ODDs. [ABSTRACT FROM AUTHOR]

Monotone Boolean circuits are circuits where each gate is either an AND gate or an OR gate. In other words, negation gates are not allowed on monotone circuits. This class of circuits has sparked the attention of researchers working in several subfields of combinatorics and complexity theory. In this work, we consider the notion of certification-width of a monotone Boolean circuit, a complexity measure that intuitively quantifies the minimum number of edges that need to be traversed by a minimal set of positive weight inputs in order to certify that a given circuit is satisfied. We call the problem of computing this invariant as Succinct Monotone Circuit Certification (SMCC). We prove that SMCC is NP-complete even when the input monotone circuit is planar. Subsequently, we show that k -SMCC , the problem parameterized by the size of the solution, is W[1]-hard, but still in W[P]. In contrast, we show that k -SMCC is fixed-parameter tractable when restricted to monotone circuits of bounded genus. [ABSTRACT FROM AUTHOR]

In the Maximum-Duo Preservation String Mapping (Max-Duo PSM) problem, the input consists of two related strings A and B of length n and a nonnegative integer k. The objective is to determine whether there exists a mapping m from the set of positions of A to the set of positions of B that maps only to positions with the same character and preserves at least k duos , which are pairs of adjacent positions. We develop a randomized algorithm that solves Max-Duo PSM in 4 k ⋅ n O (1) time, and a deterministic algorithm that solves this problem in 6.855 k ⋅ n O (1) time. The previous best known (deterministic) algorithm for this problem has (8 e) 2 k + o (k) ⋅ n O (1) running time [Beretta et al. (2016) [1,2] ]. We also show that Max-Duo PSM admits a problem kernel of size O (k 3) , improving upon the previous best known problem kernel of size O (k 6). [ABSTRACT FROM AUTHOR]

In this work we study the relationship between size and treewidth of circuits computing variants of the element distinctness function. First, we show that for each n, any circuit of treewidth t computing the element distinctness function δ : {0, 1} → {0, 1} must have size at least $\Omega (\frac {n^{2}}{2^{O(t)} \log n})$ . This result provides a non-trivial generalization of a super-linear lower bound for the size of Boolean formulas (treewidth 1) due to Nečiporuk. Subsequently, we turn our attention to read-once circuits, which are circuits where each variable labels at most one input vertex. For each n, we show that any read-once circuit of treewidth t and size s computing a variant τ : {0, 1} → {0, 1} of the element distinctness function must satisfy the inequality $t\cdot \log s \geq \Omega (\frac {n}{\log n})$ . Using this inequality in conjunction with known results in structural graph theory, we show that for each fixed graph H, read-once circuits computing τ which exclude H as a minor must have size at least Ω( n /log n). For certain well studied functions, such as the triangle-freeness function, this last lower bound can be improved to Ω( n /log 2 n). [ABSTRACT FROM AUTHOR]

The notion of directed treewidth was introduced by Johnson et al. (2001) as a first step towards an algorithmic metatheory for digraphs. They showed that some NP-complete properties such as Hamiltonicity can be decided in polynomial time on digraphs of constant directed treewidth. Nevertheless, despite more than one decade of intensive research, the list of hard combinatorial problems that are known to be solvable in polynomial time when restricted to digraphs of constant directed treewidth has remained scarce. In this work we enrich this list by providing for the first time an algorithmic metatheorem connecting the monadic second order logic of graphs to directed treewidth. We show that most of the known positive algorithmic results for digraphs of constant directed treewidth can be reformulated in terms of our metatheorem. Additionally, we show how to use our metatheorem to provide polynomial time algorithms for two classes of combinatorial problems that have not yet been studied in the context of directed width measures. More precisely, for each fixed k , w ∈ N , we show how to count in polynomial time on digraphs of directed treewidth w , the number of minimum spanning strong subgraphs that are the union of k directed paths, and the number of maximal subgraphs that are the union of k directed paths and satisfy a given minor closed property. To prove our metatheorem we devise two technical tools which we believe to be of independent interest. First, we introduce the notion of tree-zig-zag number of a digraph, a new directed width measure that is at most a constant times directed treewidth. Second, we introduce the notion of z -saturated tree slice language, a new formalism for the specification and manipulation of infinite sets of digraphs. [ABSTRACT FROM AUTHOR]

In [18] Lorenz and Juhás raised the question of whether there exists a suitable formalism for the representation of infinite families of partial orders generated by Petri nets. Restricting ourselves to bounded p/t-nets, we propose Hasse diagram generators as an answer. We show that Hasse diagram generators are expressive enough to represent the partial order language of any bounded p/t net. We prove as well that it is decidable both whether the (possibly infinite) family of partial orders represented by a given Hasse diagram generator is included in the partial order language of a given p/t-net and whether their intersection is empty. Based on this decidability result, we prove that the partial order languages of two given Petri nets can be effectively compared with respect to inclusion. Finally we address the synthesis of k-safe p/t-nets from Hasse diagram generators. [ABSTRACT FROM AUTHOR]

The notion of zig-zag number was introduced as an attempt to provide a unified algorithmic framework for directed graphs. Nevertheless, little was known about the complexity of computing this directed graph invariant. We prove that deciding whether a directed graph has zig-zag number at most k is in NP for each fixed k ≥ 0. Although for most of the natural decision problems this is an almost trivial result, settling k - zig-zag number in NP is surprisingly difficult. In addition, we prove that 2- zig-zag number is already an NP -hard problem. [ABSTRACT FROM AUTHOR]

• Parameterized analysis of a general notion of diversity of solutions that suits a large class of combinatorial problems. • Introduction of the notion of dynamic programming core. • Efficient dynamic cores for computing one solution yield efficient dynamic cores for computing a diverse set of solutions. • The notion of diversity of solutions is also compatible with certain notions of kernel. When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which – automatically – converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter. [ABSTRACT FROM AUTHOR]