Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
Highlights Conference 2013 Conference Abstract
We extend the notion of invariant elementary definability to a variety of different graph representations, including those that strictly extend the power of first-order logic with an arbitrary linear order.
I&C Journal 1998 Journal Article
We define and justify a natural sequential model of computation with a constant amount of read/write work space, despite unlimited (polynomial) access to read-only input and write-only output. The model is deterministic, uniform, and sequential. The constant work space is modeled by a finite number of destructively read boolean variables, assignable by formulas over the canonical boolean operations. We show that computation on this model is equivalent to expressibility in first-order logic, giving a duality between (read-once) constant-space serial algorithms and constant-time parallel algorithms.
CSL Conference 1996 Conference Paper
Abstract The Ordered conjecture of Kolaitis and Vardi asks whether fixed-point logic differs from first-order logic on every infinite class of finite ordered structures. In this paper, we develop the tool of bounded variable element types, and illustrate its application to this and the original conjectures of McColm, which arose from the study of inductive definability and infinitary logic on proficient classes of finite structures (those admitting an unbounded induction). In particular, for a class of finite structures, we introduce a compactness notion which yields a new proof of a ramified version of McColm's second conjecture. Furthermore, we show a connection between a model-theoretic preservation property and the Ordered Conjecture, allowing us to prove it for classes of strings (colored orderings). We also elaborate on complexity-theoretic implications of this line of research.
CSL Conference 1996 Conference Paper
Abstract We propose a natural generalization of the concept of implicit definitions over finite structures, allowing non-determinism at an intermediate level of a (deterministic) definition. These generalized implicit definitions offer more expressive power than classical implicit definitions. Moreover, their expressive power can be characterized over unordered finite structures in terms of the complexity class NP ∩ co-NP. Finally, we investigate a subclass of these where the non-determinism is restricted to the choice of a unique relation with respect to an implicit linear order, and prove that it captures UP ∩ co-UP also over the class of all finite structures. These results shed some light on the expressive power of non-deterministic primitives.
STOC Conference 1992 Conference Paper
We present a solution to the problem of assigning to each directed tree T of size n a unique isomorphism invariant name for T , using only work space O (log n ). Hence, tree isomorphism is computable in logspace. As another consequence, we obtain the corollary that the set of logspace computable queries ( Lspace ) on trees is recursively enumerable. Our results extend easily to undirected trees and even forests.
TCS Journal 1991 Journal Article
The presence of ordering appears to play an essential role in the logical expressibility of polynomial-time queries on finite structures. By examining the expressibility and complexity of inductive queries on the class of complete unordered binary trees, we are able to show that the ability to calculate cardinality is strictly less powerful than the assumption of order.