DROPS

Document

Traversal-Invariant Characterizations of Logarithmic Space

Authors: Siddharth Bhaskar, Steven Lindell, and Scott Weinstein

Published in: OASIcs, Volume 119, The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen (2024)

Abstract

We give a novel descriptive-complexity theoretic characterization of L and NL computable queries over finite structures using traversal invariance. We summarize this as (N)L = FO + (breadth-first) traversal-invariance.

Cite as

Siddharth Bhaskar, Steven Lindell, and Scott Weinstein. Traversal-Invariant Characterizations of Logarithmic Space. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:OASIcs.Tannen.2,
  author =	{Bhaskar, Siddharth and Lindell, Steven and Weinstein, Scott},
  title =	{{Traversal-Invariant Characterizations of Logarithmic Space}},
  booktitle =	{The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen},
  pages =	{2:1--2:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-320-1},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{119},
  editor =	{Amarilli, Antoine and Deutsch, Alin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.2},
  URN =		{urn:nbn:de:0030-drops-200984},
  doi =		{10.4230/OASIcs.Tannen.2},
  annote =	{Keywords: Model theory, finite model theory, descriptive complexity theory, logarithmic space, graph traversals}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2021.17

Graph Traversals as Universal Constructions

Authors: Siddharth Bhaskar and Robin Kaarsgaard

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract

We exploit a decomposition of graph traversals to give a novel characterization of depth-first and breadth-first traversals by means of 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.

Cite as

Siddharth Bhaskar and Robin Kaarsgaard. Graph Traversals as Universal Constructions. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.MFCS.2021.17,
  author =	{Bhaskar, Siddharth and Kaarsgaard, Robin},
  title =	{{Graph Traversals as Universal Constructions}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.17},
  URN =		{urn:nbn:de:0030-drops-144573},
  doi =		{10.4230/LIPIcs.MFCS.2021.17},
  annote =	{Keywords: graph traversals, adjunctions, universal constructions, category theory}
}

Search Results

Documents authored by Bhaskar, Siddharth

Traversal-Invariant Characterizations of Logarithmic Space

Abstract

Cite as

Graph Traversals as Universal Constructions

Abstract

Cite as

Thanks for your feedback!

Could not send message