Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRanked enumeration of MSO logic on words
113
0
0.0
(
0
)
Added by
Alejandro Grez
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the last years, enumeration algorithms with bounded delay have attracted a lot of attention for several data management tasks. Given a query and the data, the task is to preprocess the data and then enumerate all the answers to the query one by one and without repetitions. This enumeration scheme is typically useful when the solutions are treated on the fly or when we want to stop the enumeration once the pertinent solutions have been found. However, with the current schemes, there is no restriction on the order how the solutions are given and this order usually depends on the techniques used and not on the relevance for the user. In this paper we study the enumeration of monadic second order logic (MSO) over words when the solutions are ranked. We present a framework based on MSO cost functions that allows to express MSO formulae on words with a cost associated with each solution. We then demonstrate the generality of our framework which subsumes, for instance, document spanners and regular complex event processing queries and adds ranking to them. The main technical result of the paper is an algorithm for enumerating all the solutions of formulae in increasing order of cost efficiently, namely, with a linear preprocessing phase and logarithmic delay between solutions. The novelty of this algorithm is based on using functional data structures, in particular, by extending functional Brodal queues to suit with the ranked enumeration of MSO on words.
rate research
Read More
A tree decomposition of a graph facilitates computations by grouping vertices into bags that are interconnected in an acyclic structure, hence their importance in a plethora of problems such as query evaluation over databases and inference over probabilistic graphical models. The relative benefit from different tree decompositions is measured by diverse (sometime complex) cost functions that vary from one application to another. For generic cost functions like width and fill-in, an optimal tree decomposition can be efficiently computed in some cases, notably when the number of minimal separators is bounded by a polynomial (due to Bouchitte and Todinca), we refer to this assumption as poly-MS. To cover the variety of cost functions in need, it has recently been proposed to devise algorithms for enumerating many decomposition candidates for applications to choose from using specialized, or even machine-learned, cost functions. We explore the ability to produce a large collection of high quality tree decompositions. We present the first algorithm for ranked enumeration of the proper (non-redundant) tree decompositions, or equivalently minimal triangulations, under a wide class of cost functions that substantially generalizes the above generic ones. On the theoretical side, we establish the guarantee of polynomial delay if poly-MS is assumed, or if we are interested in tree decompositions of a width bounded by a constant. We describe an experimental evaluation on graphs of various domains (including join queries, Bayesian networks, treewidth benchmarks and random), and explore both the applicability of the poly-MS assumption and the performance of our algorithm relative to the state of the art.
We introduce MK-fuzzy automata over a bimonoid K which is related to the fuzzification of the McCarthy-Kleene logic. Our automata are inspired by, and intend to contribute to, practical applications being in development in a project on runtime network monitoring based on predicate logic. We investigate closure properties of the class of recognizable MK-fuzzy languages accepted by MK-fuzzy automata as well as of deterministically recognizable MK-fuzzy languages accepted by their deterministic counterparts. Moreover, we establish a Nivat-like result for recognizable MK-fuzzy languages. We introduce an MK-fuzzy MSO logic and show the expressive equivalence of a fragment of this logic with MK-fuzzy automata, i.e., a Buchi type theorem.
Given a (finite or infinite) subset $X$ of the free monoid $A^*$ over a finite alphabet $A$, the rank of $X$ is the minimal cardinality of a set $F$ such that $X subseteq F^*$. A submonoid $M$ generated by $k$ elements of $A^*$ is $k$-maximal if there does not exist another submonoid generated by at most $k$ words containing $M$. We call a set $X subseteq A^*$ primitive if it is the basis of a $|X|$-maximal submonoid. This extends the notion of primitive word: indeed, ${w}$ is a primitive set if and only if $w$ is a primitive word. By definition, for any set $X$, there exists a primitive set $Y$ such that $X subseteq Y^*$. The set $Y$ is therefore called a primitive root of $X$. As a main result, we prove that if a set has rank $2$, then it has a unique primitive root. This result cannot be extended to sets of rank larger than 2. For a single word $w$, we say that the set ${x,y}$ is a {em binary root} of $w$ if $w$ can be written as a concatenation of copies of $x$ and $y$ and ${x,y}$ is a primitive set. We prove that every primitive word $w$ has at most one binary root ${x,y}$ such that $|x|+|y|<sqrt{|w|}$. That is, the binary root of a word is unique provided the length of the word is sufficiently large with respect to the size of the root. Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function $theta$ is defined on $A^*$. In this setting, the notions of $theta$-power, $theta$-primitive and $theta$-root are defined, and it is shown that any word has a unique $theta$-primitive root. This result can be obtained with our approach by showing that a word $w$ is $theta$-primitive if and only if ${w, theta(w)}$ is a primitive set.
We consider the convex hull $P_{varphi}(G)$ of all satisfying assignments of a given MSO formula $varphi$ on a given graph $G$. We show that there exists an extended formulation of the polytope $P_{varphi}(G)$ that can be described by $f(|varphi|,tau)cdot n$ inequalities, where $n$ is the number of vertices in $G$, $tau$ is the treewidth of $G$ and $f$ is a computable function depending only on $varphi$ and $tau.$ In other words, we prove that the extension complexity of $P_{varphi}(G)$ is linear in the size of the graph $G$, with a constant depending on the treewidth of $G$ and the formula $varphi$. This provides a very general yet very simple meta-theorem about the extension complexity of polytopes related to a wide class of problems and graphs. As a corollary of our main result, we obtain an analogous result % for the weaker MSO$_1$ logic on the wider class of graphs of bounded cliquewidth. Furthermore, we study our main geometric tool which we term the glued product of polytopes. While the glued product of polytopes has been known since the 90s, we are the first to show that it preserves decomposability and boundedness of treewidth of the constraint matrix. This implies that our extension of $P_varphi(G)$ is decomposable and has a constraint matrix of bounded treewidth; so far only few classes of polytopes are known to be decomposable. These properties make our extension useful in the construction of algorithms.
Given a (finite or infinite) subset $X$ of the free monoid $A^*$ over a finite alphabet $A$, the rank of $X$ is the minimal cardinality of a set $F$ such that $X subseteq F^*$. We say that a submonoid $M$ generated by $k$ elements of $A^*$ is {em $k$-maximal} if there does not exist another submonoid generated by at most $k$ words containing $M$. We call a set $X subseteq A^*$ {em primitive} if it is the basis of a $|X|$-maximal submonoid. This definition encompasses the notion of primitive word -- in fact, ${w}$ is a primitive set if and only if $w$ is a primitive word. By definition, for any set $X$, there exists a primitive set $Y$ such that $X subseteq Y^*$. We therefore call $Y$ a {em primitive root} of $X$. As a main result, we prove that if a set has rank $2$, then it has a unique primitive root. To obtain this result, we prove that the intersection of two $2$-maximal submonoids is either the empty word or a submonoid generated by one single primitive word. For a single word $w$, we say that the set ${x,y}$ is a {em bi-root} of $w$ if $w$ can be written as a concatenation of copies of $x$ and $y$ and ${x,y}$ is a primitive set. We prove that every primitive word $w$ has at most one bi-root ${x,y}$ such that $|x|+|y|<sqrt{|w|}$. That is, the bi-root of a word is unique provided the word is sufficiently long with respect to the size (sum of lengths) of the root. Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function $theta$ is defined on $A^*$. In this setting, the notions of $theta$-power, $theta$-primitive and $theta$-root are defined, and it is shown that any word has a unique $theta$-primitive root. This result can be obtained with our approach by showing that a word $w$ is $theta$-primitive if and only if ${w, theta(w)}$ is a primitive set.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
