Penn Arts & Sciences Logo

Logic and Computation Seminar

Monday, October 25, 2021 - 3:30pm

Steven Lindell

Haverford College

Location

University of Pennsylvania

online

We will present the notion of invariant definability from a logical point of view, with a focus on (breadth-first) traversals over finite graphs and their connection to (nondeterministic) logarithmic space computation.  Invariant definability is a natural generalization of implicitly defined relations to those with a unique elementary interpretation relative to a definable collection of expansions called presentations.  Our focus is on ordered presentations over graphs.  When presented by a (breadth-first) traversal ordering, nonelementary notions like connectivity and acyclicity are definable in a remarkably simple way.  Using celebrated memory efficient algorithms, we show how this idea can be extended to capture all (nondeterministic) logspace computations.  Consequently, the complexity class (N)L can be characterized by first-order logic extended by (breadth-first) graph traversals.  This is joint work with Siddharth Bhaskar and Scott Weinstein.