2 citations · 4 across the 6 of their papers we have counts for
8 papers
Rational functions via recursive schemes
Siddharth Bhaskar, Jane Chandlee, Adam Jardine
We give a new characterization of the class of rational string functions from formal language theory using order-preserving interpretations with respect to a very weak monadic prog…
Graph Traversals as Universal Constructions
Siddharth Bhaskar, Robin Kaarsgaard
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 f…
Cons-free Programs and Complexity Classes between LOGSPACE and PTIME
Neil D. Jones, Siddharth Bhaskar, Cynthia Kop +1
Programming language concepts are used to give some new perspectives on a long-standing open problem: is logspace = ptime ?
Traversal-invariant characterizations of logarithmic space
Siddharth Bhaskar, Steven Lindell, Scott Weinstein
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 +…
Algorithmic Traversals of Infinite Graphs
Siddharth Bhaskar, Anton Jay Kienzle
A traversal of a connected graph is a linear ordering of its vertices all of whose initial segments induce connected subgraphs. Traversals, and their refinements such as breadth-fi…
Tameness in least fixed-point logic and McColm's conjecture
Siddharth Bhaskar, Alex Kruckman
We investigate four model-theoretic tameness properties in the context of least fixed-point logic over a family of finite structures. We find that each of these properties depends…
Thicket Density
Siddharth Bhaskar
We define a new type of "shatter function" for set systems that satisfies a Sauer-Shelah type dichotomy, but whose polynomial-growth case is governed by Shelah's 2-rank instead of…
Asymptotic Logical Uncertainty and The Benford Test
Scott Garrabrant, Siddharth Bhaskar, Abram Demski +3
We give an algorithm A which assigns probabilities to logical sentences. For any simple infinite sequence of sentences whose truth-values appear indistinguishable from a biased coi…