Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraph Traversals as Universal Constructions
53
0
0.0
(
0
)
Added by
Robin Kaarsgaard
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We exploit a decomposition of graph traversals to give a novel characterization of depth-first and breadth-first traversals as universal constructions. Specifically, we introduce functors from two different categories of edge-ordered directed graphs into two different categories of transitively closed edge-ordered graphs; one defines the lexicographic depth-first traversal and the other the lexicographic breadth-first traversal. We show that each functor factors as a composition of universal constructions, and that the usual presentation of traversals as linear orders on vertices can be recovered with the addition of an inclusion functor. Finally, we raise the question of to what extent we can recover search algorithms from the categorical description of the traversal they compute.
rate research
Read More
In general, a graph modification problem is defined by a graph modification operation $boxtimes$ and a target graph property ${cal P}$. Typically, the modification operation $boxtimes$ may be vertex removal}, edge removal}, edge contraction}, or edge addition and the question is, given a graph $G$ and an integer $k$, whether it is possible to transform $G$ to a graph in ${cal P}$ after applying $k$ times the operation $boxtimes$ on $G$. This problem has been extensively studied for particilar instantiations of $boxtimes$ and ${cal P}$. In this paper we consider the general property ${cal P}_{{phi}}$ of being planar and, moreover, being a model of some First-Order Logic sentence ${phi}$ (an FOL-sentence). We call the corresponding meta-problem Graph $boxtimes$-Modification to Planarity and ${phi}$ and prove the following algorithmic meta-theorem: there exists a function $f:Bbb{N}^{2}toBbb{N}$ such that, for every $boxtimes$ and every FOL sentence ${phi}$, the Graph $boxtimes$-Modification to Planarity and ${phi}$ is solvable in $f(k,|{phi}|)cdot n^2$ time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surface-embeddability (that are not FOL-expressible) and the second is the use of Gaifmans Locality Theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.
Accurately predicting the future motion of surrounding vehicles requires reasoning about the inherent uncertainty in driving behavior. This uncertainty can be loosely decoupled into lateral (e.g., keeping lane, turning) and longitudinal (e.g., accelerating, braking). We present a novel method that combines learned discrete policy rollouts with a focused decoder on subsets of the lane graph. The policy rollouts explore different goals given current observations, ensuring that the model captures lateral variability. Longitudinal variability is captured by our latent variable model decoder that is conditioned on various subsets of the lane graph. Our model achieves state-of-the-art performance on the nuScenes motion prediction dataset, and qualitatively demonstrates excellent scene compliance. Detailed ablations highlight the importance of the policy rollouts and the decoder architecture.
While the highly multilingual Universal Dependencies (UD) project provides extensive guidelines for clausal structure as well as structure within canonical nominal phrases, a standard treatment is lacking for many mischievous nominal phenomena that break the mold. As a result, numerous inconsistencies within and across corpora can be found, even in languages with extensive UD treebanking work, such as English. This paper surveys the kinds of mischievous nominal expressions attested in English UD corpora and proposes solutions primarily with English in mind, but which may offer paths to solutions for a variety of UD languages.
We develop category-theoretic framework for universal homogeneous objects, with some applications in the theory of Banach spaces, linear orderings, and in topology of compact spaces.
Categories over a field $k$ can be graded by different groups in a connected way; we consider morphisms between these gradings in order to define the fundamental grading group. We prove that this group is isomorphic to the fundamental group `a la Grothendieck as considered in previous papers. In case the $k$-category is Schurian generated we prove that a universal grading exists. Examples of non Schurian generated categories with universal grading, versal grading or none of them are considered.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
