Matching Items (4)
Filtering by
- All Subjects: Graph coloring
- All Subjects: Logic programming
- Genre: Academic theses
- Creators: Colbourn, Charles
Description
Different logic-based knowledge representation formalisms have different limitations either with respect to expressivity or with respect to computational efficiency. First-order logic, which is the basis of Description Logics (DLs), is not suitable for defeasible reasoning due to its monotonic nature. The nonmonotonic formalisms that extend first-order logic, such as circumscription and default logic, are expressive but lack efficient implementations. The nonmonotonic formalisms that are based on the declarative logic programming approach, such as Answer Set Programming (ASP), have efficient implementations but are not expressive enough for representing and reasoning with open domains. This dissertation uses the first-order stable model semantics, which extends both first-order logic and ASP, to relate circumscription to ASP, and to integrate DLs and ASP, thereby partially overcoming the limitations of the formalisms. By exploiting the relationship between circumscription and ASP, well-known action formalisms, such as the situation calculus, the event calculus, and Temporal Action Logics, are reformulated in ASP. The advantages of these reformulations are shown with respect to the generality of the reasoning tasks that can be handled and with respect to the computational efficiency. The integration of DLs and ASP presented in this dissertation provides a framework for integrating rules and ontologies for the semantic web. This framework enables us to perform nonmonotonic reasoning with DL knowledge bases. Observing the need to integrate action theories and ontologies, the above results are used to reformulate the problem of integrating action theories and ontologies as a problem of integrating rules and ontologies, thus enabling us to use the computational tools developed in the context of the latter for the former.
ContributorsPalla, Ravi (Author) / Lee, Joohyung (Thesis advisor) / Baral, Chitta (Committee member) / Kambhampati, Subbarao (Committee member) / Lifschitz, Vladimir (Committee member) / Arizona State University (Publisher)
Created2012
Description
Knowledge representation and reasoning is a prominent subject of study within the field of artificial intelligence that is concerned with the symbolic representation of knowledge in such a way to facilitate automated reasoning about this knowledge. Often in real-world domains, it is necessary to perform defeasible reasoning when representing default behaviors of systems. Answer Set Programming is a widely-used knowledge representation framework that is well-suited for such reasoning tasks and has been successfully applied to practical domains due to efficient computation through grounding--a process that replaces variables with variable-free terms--and propositional solvers similar to SAT solvers. However, some domains provide a challenge for grounding-based methods such as domains requiring reasoning about continuous time or resources.
To address these domains, there have been several proposals to achieve efficiency through loose integrations with efficient declarative solvers such as constraint solvers or satisfiability modulo theories solvers. While these approaches successfully avoid substantial grounding, due to the loose integration, they are not suitable for performing defeasible reasoning on functions. As a result, this expressive reasoning on functions must either be performed using predicates to simulate the functions or in a way that is not elaboration tolerant. Neither compromise is reasonable; the former suffers from the grounding bottleneck when domains are large as is often the case in real-world domains while the latter necessitates encodings to be non-trivially modified for elaborations.
This dissertation presents a novel framework called Answer Set Programming Modulo Theories (ASPMT) that is a tight integration of the stable model semantics and satisfiability modulo theories. This framework both supports defeasible reasoning about functions and alleviates the grounding bottleneck. Combining the strengths of Answer Set Programming and satisfiability modulo theories enables efficient continuous reasoning while still supporting rich reasoning features such as reasoning about defaults and reasoning in domains with incomplete knowledge. This framework is realized in two prototype implementations called MVSM and ASPMT2SMT, and the latter was recently incorporated into a non-monotonic spatial reasoning system. To define the semantics of this framework, we extend the first-order stable model semantics by Ferraris, Lee and Lifschitz to allow "intensional functions" and provide analyses of the theoretical properties of this new formalism and on the relationships between this and existing approaches.
To address these domains, there have been several proposals to achieve efficiency through loose integrations with efficient declarative solvers such as constraint solvers or satisfiability modulo theories solvers. While these approaches successfully avoid substantial grounding, due to the loose integration, they are not suitable for performing defeasible reasoning on functions. As a result, this expressive reasoning on functions must either be performed using predicates to simulate the functions or in a way that is not elaboration tolerant. Neither compromise is reasonable; the former suffers from the grounding bottleneck when domains are large as is often the case in real-world domains while the latter necessitates encodings to be non-trivially modified for elaborations.
This dissertation presents a novel framework called Answer Set Programming Modulo Theories (ASPMT) that is a tight integration of the stable model semantics and satisfiability modulo theories. This framework both supports defeasible reasoning about functions and alleviates the grounding bottleneck. Combining the strengths of Answer Set Programming and satisfiability modulo theories enables efficient continuous reasoning while still supporting rich reasoning features such as reasoning about defaults and reasoning in domains with incomplete knowledge. This framework is realized in two prototype implementations called MVSM and ASPMT2SMT, and the latter was recently incorporated into a non-monotonic spatial reasoning system. To define the semantics of this framework, we extend the first-order stable model semantics by Ferraris, Lee and Lifschitz to allow "intensional functions" and provide analyses of the theoretical properties of this new formalism and on the relationships between this and existing approaches.
ContributorsBartholomew, Michael James (Author) / Lee, Joohyung (Thesis advisor) / Bazzi, Rida (Committee member) / Colbourn, Charles (Committee member) / Fainekos, Georgios (Committee member) / Lifschitz, Vladimir (Committee member) / Arizona State University (Publisher)
Created2016
Description
Every graph can be colored with one more color than its maximum degree. A well-known theorem of Brooks gives the precise conditions under which a graph can be colored with maximum degree colors. It is natural to ask for the required conditions on a graph to color with one less color than the maximum degree; in 1977 Borodin and Kostochka conjectured a solution for graphs with maximum degree at least 9: as long as the graph doesn't contain a maximum-degree-sized clique, it can be colored with one fewer than the maximum degree colors. This study attacks the conjecture on multiple fronts. The first technique is an extension of a vertex shuffling procedure of Catlin and is used to prove the conjecture for graphs with edgeless high vertex subgraphs. This general approach also bears more theoretical fruit. The second technique is an extension of a method Kostochka used to reduce the Borodin-Kostochka conjecture to the maximum degree 9 case. Results on the existence of independent transversals are used to find an independent set intersecting every maximum clique in a graph. The third technique uses list coloring results to exclude induced subgraphs in a counterexample to the conjecture. The classification of such excludable graphs that decompose as the join of two graphs is the backbone of many of the results presented here. The fourth technique uses the structure theorem for quasi-line graphs of Chudnovsky and Seymour in concert with the third technique to prove the Borodin-Kostochka conjecture for claw-free graphs. The fifth technique adds edges to proper induced subgraphs of a minimum counterexample to gain control over the colorings produced by minimality. The sixth technique adapts a recoloring technique originally developed for strong coloring by Haxell and by Aharoni, Berger and Ziv to general coloring. Using this recoloring technique, the Borodin-Kostochka conjectured is proved for graphs where every vertex is in a large clique. The final technique is naive probabilistic coloring as employed by Reed in the proof of the Borodin-Kostochka conjecture for large maximum degree. The technique is adapted to prove the Borodin-Kostochka conjecture for list coloring for large maximum degree.
ContributorsRabern, Landon (Author) / Kierstead, Henry (Thesis advisor) / Colbourn, Charles (Committee member) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Hurlbert, Glenn (Committee member) / Arizona State University (Publisher)
Created2013
Description
Let $G=(V,E)$ be a graph. A \emph{list assignment} $L$ for $G$ is a function from
$V$ to subsets of the natural numbers. An $L$-\emph{coloring} is a function $f$
with domain $V$ such that $f(v)\in L(v)$ for all vertices $v\in V$ and $f(x)\ne f(y)$
whenever $xy\in E$. If $|L(v)|=t$ for all $v\in V$ then $L$ is a $t$-\emph{list
assignment}. The graph $G$ is $t$-choosable if for every $t$-list assignment $L$
there is an $L$-coloring. The least $t$ such that $G$ is $t$-choosable is called
the list chromatic number of $G$, and is denoted by $\ch(G)$. The complete multipartite
graph with $k$ parts, each of size $s$ is denoted by $K_{s*k}$. Erd\H{o}s et al.
suggested the problem of determining $\ensuremath{\ch(K_{s*k})}$, and showed that
$\ch(K_{2*k})=k$. Alon gave bounds of the form $\Theta(k\log s)$. Kierstead proved
the exact bound $\ch(K_{3*k})=\lceil\frac{4k-1}{3}\rceil$. Here it is proved that
$\ch(K_{4*k})=\lceil\frac{3k-1}{2}\rceil$.
An online version of the list coloring problem was introduced independently by Schauz
and Zhu. It can be formulated as a game between two players, Alice and Bob. Alice
designs lists of colors for all vertices, but does not tell Bob, and is allowed to
change her mind about unrevealed colors as the game progresses. On her $i$-th turn
Alice reveals all vertices with $i$ in their list. On his $i$-th turn Bob decides,
irrevocably, which (independent set) of these vertices to color with $i$. For a
function $l$ from $V$ to the natural numbers, Bob wins the $l$-\emph{game} if
eventually he colors every vertex $v$ before $v$ has had $l(v)+1$ colors of its
list revealed by Alice; otherwise Alice wins. The graph $G$ is $l$-\emph{online
choosable} or \emph{$l$-paintable} if Bob has a strategy to win the $l$-game. If
$l(v)=t$ for all $v\in V$ and $G$ is $l$-paintable, then $G$ is t-paintable.
The \emph{online list chromatic number }of $G$ is the least $t$ such that $G$
is $t$-paintable, and is denoted by $\ensuremath{\ch^{\mathrm{OL}}(G)}$. Evidently,
$\ch^{\mathrm{OL}}(G)\geq\ch(G)$. Zhu conjectured that the gap $\ch^{\mathrm{OL}}(G)-\ch(G)$
can be arbitrarily large. However there are only a few known examples with this gap
equal to one, and none with larger gap. This conjecture is explored in this thesis.
One of the obstacles is that there are not many graphs whose exact list coloring
number is known. This is one of the motivations for establishing new cases of Erd\H{o}s'
problem. Here new examples of graphs with gap one are found, and related technical
results are developed as tools for attacking Zhu's conjecture.
The square $G^{2}$ of a graph $G$ is formed by adding edges between all vertices
at distance $2$. It was conjectured that every graph $G$ satisfies $\chi(G^{2})=\ch(G^{2})$.
This was recently disproved for specially constructed graphs. Here it is shown that
a graph arising naturally in the theory of cellular networks is also a counterexample.
$V$ to subsets of the natural numbers. An $L$-\emph{coloring} is a function $f$
with domain $V$ such that $f(v)\in L(v)$ for all vertices $v\in V$ and $f(x)\ne f(y)$
whenever $xy\in E$. If $|L(v)|=t$ for all $v\in V$ then $L$ is a $t$-\emph{list
assignment}. The graph $G$ is $t$-choosable if for every $t$-list assignment $L$
there is an $L$-coloring. The least $t$ such that $G$ is $t$-choosable is called
the list chromatic number of $G$, and is denoted by $\ch(G)$. The complete multipartite
graph with $k$ parts, each of size $s$ is denoted by $K_{s*k}$. Erd\H{o}s et al.
suggested the problem of determining $\ensuremath{\ch(K_{s*k})}$, and showed that
$\ch(K_{2*k})=k$. Alon gave bounds of the form $\Theta(k\log s)$. Kierstead proved
the exact bound $\ch(K_{3*k})=\lceil\frac{4k-1}{3}\rceil$. Here it is proved that
$\ch(K_{4*k})=\lceil\frac{3k-1}{2}\rceil$.
An online version of the list coloring problem was introduced independently by Schauz
and Zhu. It can be formulated as a game between two players, Alice and Bob. Alice
designs lists of colors for all vertices, but does not tell Bob, and is allowed to
change her mind about unrevealed colors as the game progresses. On her $i$-th turn
Alice reveals all vertices with $i$ in their list. On his $i$-th turn Bob decides,
irrevocably, which (independent set) of these vertices to color with $i$. For a
function $l$ from $V$ to the natural numbers, Bob wins the $l$-\emph{game} if
eventually he colors every vertex $v$ before $v$ has had $l(v)+1$ colors of its
list revealed by Alice; otherwise Alice wins. The graph $G$ is $l$-\emph{online
choosable} or \emph{$l$-paintable} if Bob has a strategy to win the $l$-game. If
$l(v)=t$ for all $v\in V$ and $G$ is $l$-paintable, then $G$ is t-paintable.
The \emph{online list chromatic number }of $G$ is the least $t$ such that $G$
is $t$-paintable, and is denoted by $\ensuremath{\ch^{\mathrm{OL}}(G)}$. Evidently,
$\ch^{\mathrm{OL}}(G)\geq\ch(G)$. Zhu conjectured that the gap $\ch^{\mathrm{OL}}(G)-\ch(G)$
can be arbitrarily large. However there are only a few known examples with this gap
equal to one, and none with larger gap. This conjecture is explored in this thesis.
One of the obstacles is that there are not many graphs whose exact list coloring
number is known. This is one of the motivations for establishing new cases of Erd\H{o}s'
problem. Here new examples of graphs with gap one are found, and related technical
results are developed as tools for attacking Zhu's conjecture.
The square $G^{2}$ of a graph $G$ is formed by adding edges between all vertices
at distance $2$. It was conjectured that every graph $G$ satisfies $\chi(G^{2})=\ch(G^{2})$.
This was recently disproved for specially constructed graphs. Here it is shown that
a graph arising naturally in the theory of cellular networks is also a counterexample.
ContributorsWang, Ran (Author) / Kierstead, H.A. (Thesis advisor) / Colbourn, Charles (Committee member) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Sen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2015