Zobrazeno 1 - 10
of 35
pro vyhledávání: '"Bhaskar, Siddharth"'
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 programming language. This refines the known characterization of rational
Externí odkaz:
http://arxiv.org/abs/2302.03074
Autor:
Bhaskar, Siddharth, Kaarsgaard, Robin
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
Externí odkaz:
http://arxiv.org/abs/2104.14877
Publikováno v:
EPTCS 320, 2020, pp. 65-79
Programming language concepts are used to give some new perspectives on a long-standing open problem: is logspace = ptime ?
Comment: In Proceedings VPT/HCVS 2020, arXiv:2008.02483
Comment: In Proceedings VPT/HCVS 2020, arXiv:2008.02483
Externí odkaz:
http://arxiv.org/abs/2008.02932
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.
Externí odkaz:
http://arxiv.org/abs/2006.07067
Autor:
Bhaskar, Siddharth, Kienzle, Anton Jay
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-first and depth-first traversals, are computed by various graph searchin
Externí odkaz:
http://arxiv.org/abs/1810.09974
Autor:
Bhaskar, Siddharth, Kruckman, Alex
Publikováno v:
Logical Methods in Computer Science, Volume 17, Issue 1 (January 22, 2021) lmcs:4419
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 only on the elementary (i.e., first-order) limit theory, and we comple
Externí odkaz:
http://arxiv.org/abs/1708.00148
Autor:
Bhaskar, Siddharth
Publikováno v:
J. symb. log. 86 (2021) 110-127
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 VC dimension. We identify the rate of growth of this shatter function,
Externí odkaz:
http://arxiv.org/abs/1702.03956
Autor:
Bhaskar, Siddharth1 (AUTHOR) bhask2sk@jmu.edu, Kop, Cynthia2 (AUTHOR), Simonsen, Jakob Grue3 (AUTHOR)
Publikováno v:
Theory of Computing Systems. Jun2023, Vol. 67 Issue 3, p437-472. 36p.
Autor:
Garrabrant, Scott, Bhaskar, Siddharth, Demski, Abram, Garrabrant, Joanna, Koleszarik, George, Lloyd, Evan
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 coin that outputs "true" with probability p, we have that the sequence of
Externí odkaz:
http://arxiv.org/abs/1510.03370
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.