We study algorithms for
♯
SAT
and its generalized version
♯
GENSAT
, the problem of computing the number of satisfying assignments of a set of propositional clauses
Σ
. For this purpose we consider ...the clauses given by their incidence graph, a signed bipartite graph
SI
(
Σ
)
, and its derived graphs
I
(
Σ
)
and
P
(
Σ
)
.
It is well known, that, given a graph of tree-width
k, a
k-tree decomposition can be found in polynomial time. Very recently Oum and Seymour have shown that, given a graph of clique-width
k, a
(
2
3
k
+
2
-
1
)
-parse tree witnessing clique-width can be found in polynomial time.
In this paper we present an algorithm for
♯
GENSAT
for formulas of bounded tree-width
k which runs in time
4
k
(
n
+
n
2
·
log
2
(
n
)
)
, where
n is the size of the input. The main ingredient of the algorithm is a splitting formula for the number of satisfying assignments for a set of clauses
Σ
where the incidence graph
I
(
Σ
)
is a union of two graphs
G
1
and
G
2
with a shared induced subgraph
H of size at most
k. We also present analogue improvements for algorithms for formulas of bounded clique-width which are given together with their derivation.
This considerably improves results for
♯
SAT
, and hence also for SAT, previously obtained by Courcelle et al. On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic, Discrete Appl. Math. 108 (1–2) (2001) 23–52.
In this paper we argue that the traditional syllabus of logic courses for computer science is outdated and missing its purposes, therefore contributing to the gradual relegation of logic from the ...computing curricula. We further provide some practical recommendations and directions that need to be considered in the adaptation of the logic course syllabi to the needs of modern computing practitioners.
Endogenous Group Formation via Unproductive Costs AIMONE, JASON A.; IANNACCONE, LAURENCE R.; MAKOWSKY, MICHAEL D. ...
The Review of economic studies,
10/2013, Letnik:
80, Številka:
4 (285)
Journal Article
Recenzirano
Odprti dostop
Sacrifice is widely believed to enhance cooperation in churches, communes, gangs, clans, military units, and many other groups. We find that sacrifice can also work in the lab, apart from special ...ideologies, identities, or interactions. Our subjects play a modified VCM game—one in which they can voluntarily join groups that provide reduced rates of return on private investment. This leads to both endogenous sorting (because free-riders tend to reject the reduced-rate option) and substitution (because reduced private productivity favours increased club involvement). Seemingly unproductive costs thus serve to screen out free-riders, attract conditional cooperators, boost club production, and increase member welfare. The sacrifice mechanism is simple and particularly useful where monitoring difficulties impede punishment, exclusion, fees, and other more standard solutions.
The classical Feferman–Vaught Theorem for First Order Logic explains how to compute the truth value of a first order sentence in a generalized product of first order structures by reducing this ...computation to the computation of truth values of other first order sentences in the factors and evaluation of a monadic second order sentence in the index structure. This technique was later extended by Läuchli, Shelah and Gurevich to monadic second order logic. The technique has wide applications in decidability and definability theory.
Here we give a unified presentation, including some new results, of how to use the Feferman–Vaught Theorem, and some new variations thereof, algorithmically in the case of Monadic Second Order Logic
MSOL.
We then extend the technique to graph polynomials where the range of the summation of the monomials is definable in
MSOL. Here the Feferman–Vaught Theorem for these polynomials generalizes well known splitting theorems for graph polynomials. Again, these can be used algorithmically.
Finally, we discuss extensions of
MSOL for which the Feferman–Vaught Theorem holds as well.
Chomsky and Schützenberger showed in 1963 that the sequence dL(n), which counts the number of words of a given length n in a regular language L, satisfies a linear recurrence relation with constant ...coefficients for n, i.e., it is C-finite. It follows that every sequence s(n) which satisfies a linear recurrence relation with constant coefficients can be represented as dL1(n)−dL2(n) for two regular languages. We view this as a representation theorem for C-finite sequences. Holonomic or P-recursive sequences are sequences which satisfy a linear recurrence relation with polynomial coefficients. q-Holonomic sequences are the q-analog of holonomic sequences. In this paper we prove representation theorems of holonomic and q-holonomic sequences based on position specific weights on words, and for holonomic sequences, without using weights, based on sparse regular languages.
•We prove representation theorems for sequences with recurrence relations.•(q-)Holonomic sequences are captured by appropriate logical interpretations.•Representations based on positional weights of words in regular languages are shown.•A weightless sparse-structures representation is given for holonomic sequences only.
We outline a general theory of graph polynomials which covers all the examples we found in the vast literature, in particular, the chromatic polynomial, various generalizations of the Tutte ...polynomial, matching polynomials, interlace polynomials, and the cover polynomial of digraphs. We introduce two classes of (hyper)graph polynomials definable in second order logic, and outline a research program for their classification in terms of definability and complexity considerations, and various notions of reducibilities.
Inspired by the study of community structure in connection networks, we introduce the graph polynomial
Q
(
G
;
x
,
y
)
, the bivariate generating function which counts the number of connected ...components in induced subgraphs.
We give a recursive definition of
Q
(
G
;
x
,
y
)
using vertex deletion, vertex contraction and deletion of a vertex together with its neighborhood and prove a universality property. We relate
Q
(
G
;
x
,
y
)
to other known graph invariants and graph polynomials, among them partition functions, the Tutte polynomial, the independence and matching polynomials, and the universal edge elimination polynomial introduced by I. Averbouch et al. (2008)
5.
We show that
Q
(
G
;
x
,
y
)
is vertex reconstructible in the sense of Kelly and Ulam, and discuss its use in computing residual connectedness reliability. Finally we show that the computation of
Q
(
G
;
x
,
y
)
is
♯
P
-hard, but fixed parameter tractable for graphs of bounded tree-width and clique-width.
A logician's view of graph polynomials Makowsky, J.A.; Ravve, E.V.; Kotek, T.
Annals of pure and applied logic,
September 2019, 2019-09-00, Letnik:
170, Številka:
9
Journal Article
Recenzirano
Odprti dostop
Graph polynomials are graph parameters invariant under graph isomorphisms which take values in a polynomial ring with a fixed finite number of indeterminates. We study graph polynomials from a model ...theoretic point of view. In this paper we distinguish between the graph theoretic (semantic) and the algebraic (syntactic) meaning of graph polynomials. Graph polynomials appear in the literature either as generating functions, as generalized chromatic polynomials, or as polynomials derived via determinants of adjacency or Laplacian matrices. We show that these forms are mutually incomparable, and propose a unified framework based on definability in Second Order Logic. We show that this comprises virtually all examples of graph polynomials with a fixed finite set of indeterminates. Finally we show that the location of zeros and stability of graph polynomials is not a semantic property. The paper emphasizes a model theoretic view. It gives a unified exposition of classical results in algebraic combinatorics together with new and some of our previously obtained results scattered in the graph theoretic literature.
We discuss the parametrized complexity of counting and evaluation problems on graphs where the range of counting is definable in monadic second-order logic (MSOL). We show that for bounded tree-width ...these problems are solvable in polynomial time. The same holds for bounded clique width in the cases, where the decomposition, which establishes the bound on the clique-width, can be computed in polynomial time and for problems expressible by monadic second-order formulas without edge set quantification. Such quantifications are allowed in the case of graphs with bounded tree-width. As applications we discuss in detail how this affects the parametrized complexity of the permanent and the hamiltonian of a matrix, and more generally, various generating functions of MSOL definable graph properties. Finally, our results are also applicable to
SAT and ♯
SAT.
PDF
